题解 | 气球谜题

def solve(n, a_str, t_list):
    a = list(map(int, a_str))  # 0/1/2
    t = t_list

    # 预处理：计算前缀和 s[0], s[1], s[2]
    s = [[0] * (n + 1) for _ in range(3)]
    for i in range(n):
        for j in range(3):
            s[j][i + 1] = s[j][i]
        s[a[i]][i + 1] += t[i]

    ans = float('inf')

    # 手动枚举所有排列
    orders = [
        [0, 1, 2],
        [0, 2, 1],
        [1, 0, 2],
        [1, 2, 0],
        [2, 0, 1],
        [2, 1, 0],
    ]

    for x in orders:
        first_sum = s[x[0]][n] + s[x[1]][n]

        mn = [0] * (n + 1)
        cur_min = 0
        for i in range(1, n + 1):
            diff = s[x[1]][i] - s[x[0]][i]
            cur_min = min(cur_min, diff)
            mn[i] = cur_min

        for j in range(n + 1):
            res = first_sum + s[x[2]][j] - s[x[1]][j] + mn[j]
            if res < ans:
                ans = res

    return ans

# 示例使用
if __name__ == "__main__":
    import sys
    input = sys.stdin.readline
    n = int(input())
    a_str = input().strip()
    t_list = list(map(int, input().split()))
    print(solve(n, a_str, t_list))