結果

問題 No.2423 Merge Stones
ユーザー gew1fw
提出日時 2025-06-12 14:46:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,997 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 69,056 KB
最終ジャッジ日時 2025-06-12 14:48:27
合計ジャッジ時間 6,596 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    n, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))
    
    INF = -1 << 60
    max_color = 50
    
    # 复制数组处理环形结构
    extended_A = A * 2
    extended_C = C * 2
    size = 2 * n
    
    # 初始化动态规划
    dp = [ [ [INF]*(max_color+1) for _ in range(size+1) ] for __ in range(size+1) ]
    for i in range(size):
        c = extended_C[i]
        dp[i][i][c] = extended_A[i]
    
    # 按区间长度处理
    for l in range(1, n+1):
        for i in range(size):
            j = i + l - 1
            if j >= size:
                break
            # 尝试将区间拆分成k和k+1两部分
            for k in range(i, j):
                # 遍历i到k的所有可能颜色c1
                for c1 in range(max_color+1):
                    if dp[i][k][c1] == INF:
                        continue
                    # 遍历k+1到j的所有可能颜色c2
                    for c2 in range(max_color+1):
                        if dp[k+1][j][c2] == INF:
                            continue
                        if abs(c1 - c2) > K:
                            continue
                        new_sum = dp[i][k][c1] + dp[k+1][j][c2]
                        # 可以选择c1或c2作为合并后的颜色
                        for c in [c1, c2]:
                            if new_sum > dp[i][j][c]:
                                dp[i][j][c] = new_sum
    
    max_total = 0
    # 检查所有可能的区间起点i，长度<=n
    for i in range(n):
        for j in range(i, i + n):
            if j >= size:
                break
            # 取区间i到j的所有颜色中的最大值
            for c in range(max_color+1):
                if dp[i][j][c] > max_total:
                    max_total = dp[i][j][c]
    
    print(max_total)

if __name__ == "__main__":
    main()
0