题解 | 气球谜题

【Python3】输出和C++版一致，但提交不通过，怀疑是系统问题。纯纯浪费我时间。

末尾附赠一个测试用例。

from itertools import permutations

n = int(input())
s = input()
t = list(map(int, input().split()))

pre = [[0, 0, 0] for _ in range(n + 1)]
for i in range(1, n + 1):
    pre[i][0] = pre[i - 1][0]
    pre[i][1] = pre[i - 1][1]
    pre[i][2] = pre[i - 1][2]
    if s[i-1] == '0':
        pre[i][1] += t[i-1]
        pre[i][2] += t[i-1]
    elif s[i-1] == '1':
        pre[i][0] += t[i-1]
        pre[i][2] += t[i-1]
    else:
        pre[i][0] += t[i-1]
        pre[i][1] += t[i-1]

ans = sum(t)
color = [0, 1, 2]
mn = [0] * (n + 1)
for each in permutations(color):
    a, b, c = each
    mn[1] = pre[1][a] - pre[1][b]
    for i in range(2, n + 1):
        mn[i] = min(mn[i-1], pre[i][a] - pre[i][b])

    for j in range(n, 0, -1):
        ans = min(ans, pre[n][c] - pre[j-1][c] + pre[j-1][b] + mn[j-1])
print(ans)

# len(s) = 1000
0212010212011021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201021201002120102120110212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010212010

# len(t) = 1000
14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2 14 17 3 10 19 5 12 8 15 20 11 16 4 9 18 6 13 7 1 2