結果

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

ソースコード

diff # 

def main():
    import sys
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))
    
    # 扩展数组处理环情况
    A_new = A + A
    C_new = C + C
    size = 2*N

    # 预处理颜色对是否可以合并
    max_color = max(C_new)
    can_merge = [[False]*(max_color+1) for _ in range(max_color+1)]
    for c1 in range(max_color+1):
        for c2 in range(max_color+1):
            if abs(c1 - c2) <= K:
                can_merge[c1][c2] = True

    # 初始化动态规划表
    dp = [[dict() for _ in range(size)] for __ in range(size)]
    for i in range(size):
        dp[i][i][C_new[i]] = A_new[i]

    # 填充动态规划表
    for l in range(2, N+1):
        for i in range(size - l +1):
            j = i + l -1
            dp[i][j] = {}
            for k in range(i, j):
                if not dp[i][k] or not dp[k+1][j]:
                    continue
                for c1 in dp[i][k]:
                    for c2 in dp[k+1][j]:
                        if can_merge[c1][c2]:
                            new_power = dp[i][k][c1] + dp[k+1][j][c2]
                            for new_c in [c1, c2]:
                                if new_c in dp[i][j]:
                                    if dp[i][j][new_c] < new_power:
                                        dp[i][j][new_c] = new_power
                                else:
                                    dp[i][j][new_c] = new_power

    # 寻找最大值
    max_power = 0
    for i in range(N):
        j = i + N -1
        if j >= size:
            continue
        if dp[i][j]:
            current_max = max(dp[i][j].values())
            if current_max > max_power:
                max_power = current_max

    for i in range(size):
        for j in range(i, min(i + N, size)):
            if j - i +1 > N:
                continue
            if dp[i][j]:
                current_max = max(dp[i][j].values())
                if current_max > max_power:
                    max_power = current_max

    print(max_power)

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