結果

問題 No.2591 安上がりな括弧列
ユーザー flippergo
提出日時 2025-07-20 20:52:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 998 bytes
コンパイル時間 403 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 109,208 KB
最終ジャッジ日時 2025-07-20 20:52:40
合計ジャッジ時間 4,515 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
S = "0"+input().strip()
A = [0]+list(map(int,input().split()))
INFTY = 10**12+100
dp = [[INFTY for _ in range(2*N+1)] for _ in range(2*N+1)]
for i in range(1,2*N):
    if S[i]=="(" and S[i+1]==")":
        dp[i][i+1] = 0
    elif S[i]=="(" and S[i+1]=="(":
        dp[i][i+1] = A[i+1]
    elif S[i]==")" and S[i+1]==")":
        dp[i][i+1] = A[i]
    else:  # S[i]==")" and S[i+1]=="("
        dp[i][i+1] = A[i]+A[i+1]
for k in range(4,2*N+1,2):
    for i in range(1,2*N):
        j = i+k-1
        if j>2*N:break
        dp[i][j] = min(dp[i][j-2]+dp[j-1][j],dp[i][i+1]+dp[i+2][j])
        if S[i]=="(" and S[j]==")":
            dp[i][j] = min(dp[i][j],dp[i+1][j-1])
        elif S[i]=="(" and S[j]=="(":
            dp[i][j] = min(dp[i][j],dp[i+1][j-1]+A[j])
        elif S[i]==")" and S[j]==")":
            dp[i][j] = min(dp[i][j],dp[i+1][j-1]+A[i])
        else:  # S[i]==")" and S[j]=="("
            dp[i][j] = min(dp[i][j],dp[i+1][j-1]+A[i]+A[j])
print(dp[1][2*N])
0