差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/19] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/19] – ikatakos | ||
|---|---|---|---|
| 行 363: | 行 363: | ||
| <sxh python> | <sxh python> | ||
| - | from collections | + | from bisect |
| - | from operator import itemgetter | + | |
| n, a, b = map(int, input().split()) | n, a, b = map(int, input().split()) | ||
| - | ppp = list(map(int, input().split())) | + | ppp = map(int, input().split()) |
| - | qqq = list(map(itemgetter(0), sorted(enumerate(ppp, | + | qqq = [0] * n |
| + | for i, p in enumerate(ppp, | ||
| + | qqq[p - 1] = i | ||
| - | dp = {0: 0} | + | dp = [(0, 0)] |
| for i in qqq: | for i in qqq: | ||
| - | | + | |
| - | for j, cost in dp.items(): | + | |
| - | if j < i: | + | |
| - | ndp[i] = min(ndp[i], cost) | + | ndp.append((i, stay_cost)) |
| - | ndp[j] = min(ndp[j], cost + b) | + | remain |
| - | else: | + | for j, cost in remain: |
| - | ndp[j] = min(ndp[j], cost + a) | + | if stay_cost > cost + a: |
| + | ndp.append((j, cost + a)) | ||
| + | break | ||
| + | ndp.extend((j, cost + a) for j, cost in remain) | ||
| dp = ndp | dp = ndp | ||
| - | + | print(dp[-1][1]) | |
| - | print(min(dp.values())) | + | |
| </ | </ | ||
