Problem:
 Score : 1000 points    Problem Statement You are given a permutation p = (p_1, \ldots, p_N) of \{ 1, \ldots, N \} .
You can perform the following two kinds of operations repeatedly in any order:   Pay a cost A . Choose integers l and r ( 1 \leq l < r \leq N ), and shift (p_l, \ldots, p_r) to the left by one. That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l , respectively.  Pay a cost B . Choose integers l and r ( 1 \leq l < r \leq N ), and shift (p_l, \ldots, p_r) to the right by one.  That is, replace p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r with p_r, p_l, \ldots, p_{r - 2}, p_{r - 1} , respectively.   Find the minimum total cost required to sort p in ascending order.      Constraints  All values in input are integers.  1 \leq N \leq 5000  1 \leq A, B \leq 10^9  (p_1 \ldots, p_N) is a permutation of \{ 1, \ldots, N \} .         Input Input is given from Standard Input in the following format:  N  A  B  p_1  \cdots  p_N       Output Print the minimum total cost required to sort p in ascending order.        Sample Input 1 3 20 30
3 1 2      Sample Output 1 20  Shifting (p_1, p_2, p_3) to the left by one results in p = (1, 2, 3) .       Sample Input 2 4 20 30
4 2 3 1      Sample Output 2 50  One possible sequence of operations is as follows:   Shift (p_1, p_2, p_3, p_4) to the left by one. Now we have p = (2, 3, 1, 4) .  Shift (p_1, p_2, p_3) to the right by one. Now we have p = (1, 2, 3, 4) .   Here, the total cost is 20 + 30 = 50 .       Sample Input 3 1 10 10
1      Sample Output 3 0       Sample Input 4 4 1000000000 1000000000
4 3 2 1      Sample Output 4 3000000000       Sample Input 5 9 40 50
5 3 4 7 6 1 2 9 8      Sample Output 5 220

Solution (Python):
N,A,B=map(int,input().split())
p=list(map(int,input().split()))
p=[p[i]-1 for i in range(N)]

dp=[[0 for i in range(N+1)] for j in range(N)]

for j in range(N+1):
    if p[0]<=j:
        dp[0][j]=0
    else:
        dp[0][j]=A

for i in range(1,N):
    for j in range(N+1):
        if p[i]<=j:
            dp[i][j]=min(dp[i-1][p[i]],dp[i-1][j]+B)
        else:
            dp[i][j]=dp[i-1][j]+A

print(dp[-1][N])

Solution (Python):
import sys
input=sys.stdin.readline

N,A,B=map(int,input().split())
P=list(map(int,input().split()))

data=[0]*(N+1)
flag=[0]*(N+1)
for i in range(N):
    p=P[i]
    flag[p]=1
    cnt=0
    for j in range(p+1,N+1):
        if flag[j]==0:
            data[j]=data[j-1]
        else:
            cnt+=1
            data[j]=min(cnt*A+data[p-1],data[j]+B)

print(data[-1])

Solution (Python):
N, A, B = map(int, input().split())
P = [int(a) - 1 for a in input().split()]
X = [0] * N
for i in range(N):
    pre = X
    X = [0] * N
    mi = pre[0]
    for j in range(N):
        mi = min(mi, pre[j])
        X[j] = mi + (A if j < P[i] else B if j > P[i] else 0)
print(min(X))

Solution (Python):

"""

Writer: SPD_9X2
https://atcoder.jp/contests/agc032/tasks/agc032_d

圧倒的挿入ソート
https://atcoder.jp/contests/abc006/tasks/abc006_4
これの、左右のコストが違うVer

最長部分増加列を計算すれば、A=Bの時の答えは分かる
その時の答えは, A * (N - 最長部分増加列の長さ)

残りのカードが昇順になるように抜き出し、適切な場所に戻す。
最長部分列として採用する or しないで dp?

dp[i][部分増加列の最後の数字] = i番目まで見た時のコストの最小値 かな？

増加列の最後に足せば、コストはかからない
足さないとき、最後の数字より大きければ、A払う
小さければ、B払う

O(N**2)で解けた？
"""

N,A,B = map(int,input().split())

p = list(map(int,input().split()))

dp = [float("inf")] * (N+1)
dp[0] = 0

for i in range(N):

    ndp = [float("inf")] * (N+1)

    for j in range(N+1):

        if p[i] >= j: 
            ndp[j] = min(ndp[j] , dp[j] + A)
            ndp[p[i]] = min(ndp[p[i]] , dp[j])

        else: 
            ndp[j] = min(ndp[j] , dp[j] + B)

    dp = ndp
print (min(dp))

Solution (Python):
n, a, b = map(int, input().split())
p = list(map(int, input().split()))

INF = 10**13
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
	for j in range(n+1):
		if j < p[i]:
			dp[i+1][p[i]] = min(dp[i+1][p[i]], dp[i][j])
			dp[i+1][j] = min(dp[i+1][j], dp[i][j] + a)
		else:
			dp[i+1][j] = min(dp[i+1][j], dp[i][j] + b)

print(min(dp[n]))

Solution (Python):
import sys
readline = sys.stdin.readline

N, A, B = map(int, readline().split())
P = list(map(int, readline().split()))

INF = 1<<64

dp = [INF]*(N+1)
dp[0] = 0

for i in range(N):
    p = P[i]
    dp2 = [INF]*(N+1)
    for j in range(N+1):
        if p < j:
            dp2[j] = dp[j] + B
        if j < p:
            dp2[p] = min(dp2[p], dp[j])
            dp2[j] = dp[j] + A
    dp = dp2
print(min(dp))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    N, R, L = map(int, input().split())
    P = list(map(int, input().split()))

    val2idx = [0] * (N+1)
    for i, p in enumerate(P):
        val2idx[p] = i + 1
    bigger = [[0] * (N+1) for _ in range(N+1)]
    for p in range(1, N+1):
        for j in range(N):
            if P[j] > p:
                bigger[p][j+1] = bigger[p][j] + 1
            else:
                bigger[p][j + 1] = bigger[p][j]
    
    inf = 10**14
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0

    for p in range(1, N+1):
        i = val2idx[p]
        for j in range(N+1):
            if i > j:
                dp[p][j] = min(dp[p][j], dp[p-1][j] + L)
                dp[p][i] = min(dp[p][i], dp[p-1][j] + R * (bigger[p][i] - bigger[p][j]))
            else:
                dp[p][j] = min(dp[p][j], dp[p - 1][j])
    print(min(dp[-1]))
    


if __name__ == '__main__':
    main()

Solution (Python):
from numpy import *
N,A,B,*P=map(int,open(0).read().split());d=full(N+1,1<<60,'int');d[0]=0
for p in P:d[p]=min(d[:p]);d[p+1:]+=B;d[:p]+=A
print(min(d))

Solution (Python):
import numpy as np
N,A,B,*P=map(int,open(0).read().split())
dp=np.full(N+1,10**18,np.int64)
dp[0]=0
for p in P:
    dp[p]=min(dp[:p])
    dp[p+1:]+=B
    dp[:p]+=A
print(min(dp))

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np

"""
各数字ごとに左移動・右移動・そのまま使う。全部コスト1ならLIS。
左から見て、「最後にそのまま使った数、そこまでの数を並べるコスト」を持ってdp。
"""

N,A,B = map(int,input().split())
P = [int(x) for x in input().split()]

INF = 10**18
dp = np.full(N+1,INF,dtype=np.int64)
dp[0] = 0
for p in P:
    
    dp[p] = dp[:p].min()
    
    dp[p+1:] += B
    
    dp[:p] += A

answer = dp.min()
print(answer)

Solution (Python):
n, a, b = map(int, input().split())
dp = [0] + [2 ** 60] * n
p = list(map(int, input().split()))
for i in range(n):
	dp[i + 1] = dp[0]
	dp[0] += a
	for j in range(i):
		if p[j] < p[i]: dp[i + 1] = min(dp[i + 1], dp[j + 1])
		dp[j + 1] += [b, a][p[j] < p[i]]
print(min(dp))

Solution (Python):
N,A,B=map(int,input().split())
P=[int(i) for i in input().split()]
s=1e19
d=[s]*(N+1)
d[0]=0
for i in range(N):
    e=[s]*(N+1)
    for j in range(N+1):
        if j < P[i]:
            e[P[i]]=min(e[P[i]],d[j])
            e[j]=min(e[j],d[j]+A)
        else:
            e[j]=min(e[j],d[j]+B)
    d=e
print(min(d))

Solution (Python):
N,A,B=map(int,input().split())
P=[int(i) for i in input().split()]
dp=[10**19]*(N+1)
dp[0]=0
for i in range(1,N+1):
    ndp=[10**19]*(N+1)
    for j in range(N+1):
        if j < P[i-1]:
            ndp[P[i-1]]=min(ndp[P[i-1]],dp[j])
            ndp[j]=min(ndp[j],dp[j]+A)
        else:
            ndp[j]=min(ndp[j],dp[j]+B)
    dp=ndp
print(min(dp))

Solution (Python):
from bisect import bisect
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = map(itemgetter(0), sorted(enumerate(ppp, start=1), key=itemgetter(1)))

dp = [(0, 0)]
for i in qqq:
    s = bisect(dp, (i,))
    ndp = [(j, cost + b) for j, cost in dp[:s]]
    stay_cost = dp[s - 1][1]
    ndp.append((i, stay_cost))
    remain = iter(dp[s:])
    for j, cost in remain:
        if stay_cost > cost + a:
            ndp.append((j, cost + a))
            break
    ndp.extend((j, cost + a) for j, cost in remain)
    dp = ndp
print(dp[-1][1])

Solution (Python):
from bisect import bisect

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [0] * n
for i, p in enumerate(ppp, start=1):
    qqq[p - 1] = i

dp = [(0, 0)]
for i in qqq:
    s = bisect(dp, (i,))
    ndp = [(j, cost + b) for j, cost in dp[:s]]
    stay_cost = dp[s - 1][1]
    ndp.append((i, stay_cost))
    remain = iter(dp[s:])
    for j, cost in remain:
        if stay_cost > cost + a:
            ndp.append((j, cost + a))
            break
    ndp.extend((j, cost + a) for j, cost in remain)
    dp = ndp
print(dp[-1][1])

Solution (Python):
from bisect import bisect
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [i for i, p in sorted(enumerate(ppp, start=1), key=itemgetter(1))]
INF = 10 ** 15

dp = [(0, 0)]
for i in qqq:
    ndp = []
    s = bisect(dp, (i,))
    tmp_min = INF
    for j, cost in dp[:s]:
        cost += b
        ndp.append((j, cost))
        tmp_min = cost
    stay_cost = dp[s - 1][1]
    if tmp_min > stay_cost:
        ndp.append((i, stay_cost))
        tmp_min = stay_cost
    for j, cost in dp[s:]:
        cost += a
        if tmp_min > cost:
            ndp.append((j, cost))
            tmp_min = cost
    dp = ndp

print(dp[-1][1])

Solution (Python):
import sys
readline = sys.stdin.readline

N, A, B = map(int, readline().split())
*P, = map(int, readline().split())
Q = [0]*N
for i, p in enumerate(P):
    Q[p-1] = i

INF = 10**18
dp = [[INF]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    qi = Q[i]
    for j in range(N):
        v = dp[i][j]
        dp[i+1][j] = min(dp[i+1][j], v + (A if qi < j else B))
        dp[i][j+1] = min(dp[i][j+1], v)
        if Q[i] == j:
            dp[i+1][j+1] = min(dp[i+1][j+1], v)
for i in range(N):
    dp[i+1][N] = min(dp[i+1][N], dp[i][N] + A)
for j in range(N):
    dp[N][j+1] = min(dp[N][j+1], dp[N][j])
sys.stdout.write("%d\n" % dp[N][N])

Solution (Python):
n, a, b = map(int, input().split())
dp = [2 ** 60] * (n + 1)
dp[0] = 0
p = list(map(int, input().split()))
for i in range(n):
    dp[i + 1] = dp[0]
    dp[0] += a
    for j in range(i):
        if p[j] < p[i]:
            dp[i + 1] = min(dp[i + 1], dp[j + 1])
            dp[j + 1] += a
        else:
            dp[j + 1] += b
print(min(dp))