Submission #64557828

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inf = 1 << 60
n = int(input())
c = list(map(int, input().split()))
x = list(map(int, input().split()))
C = c + c
ans=inf
for s in range(n):
    goal = C[s : s + n]
    dp = [[inf] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1 + x[goal[i] - 1]
    for i in range(2, n + 1):
        for l in range(0, n - i + 1):
            r = l + i - 1
            dp[l][r] = min(dp[l][r],dp[l][r - 1] + 1 + x[goal[r] - 1])
            for k in range(l, r):
                if goal[k] == goal[r]:
                    c = dp[l][k]+r-k
                    if k + 1 < r:
                        c += dp[k + 1][r - 1]
                    if c < dp[l][r]:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

inf = 1 << 60
n = int(input())
c = list(map(int, input().split()))
x = list(map(int, input().split()))
C = c + c
ans=inf
for s in range(n):
    goal = C[s : s + n]
    dp = [[inf] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1 + x[goal[i] - 1]
    for i in range(2, n + 1):
        for l in range(0, n - i + 1):
            r = l + i - 1
            dp[l][r] = min(dp[l][r],dp[l][r - 1] + 1 + x[goal[r] - 1])
            for k in range(l, r):
                if goal[k] == goal[r]:
                    c = dp[l][k]+r-k
                    if k + 1 < r:
                        c += dp[k + 1][r - 1]
                    if c < dp[l][r]:
                        dp[l][r] = c
    ans=min(dp[0][-1],ans)
print(ans)

Submission Info

Judge Result