結果

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

ソースコード

diff # 

import sys

def main():
    n, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))

    max_color = 50
    size = 2 * n

    # 复制数组
    A_ = A * 2
    C_ = C * 2

    # 预处理颜色对是否满足条件
    color_diff = [[False] * (max_color + 1) for _ in range(max_color + 1)]
    for c in range(1, max_color + 1):
        for d in range(1, max_color + 1):
            if abs(c - d) <= K:
                color_diff[c][d] = True

    # 初始化dp数组
    INF = float('-inf')
    dp = [[[INF] * (max_color + 1) for _ in range(size)] for __ in range(size)]
    for i in range(size):
        c_i = C_[i]
        dp[i][i][c_i] = A_[i]

    # 处理区间长度从2到n
    for l in range(2, n + 1):
        for i in range(size):
            j = i + l - 1
            if j >= size:
                continue
            # 遍历分割点m
            for m in range(i, j):
                # 遍历颜色c和d
                for c in range(1, max_color + 1):
                    if dp[i][m][c] == INF:
                        continue
                    for d in range(1, max_color + 1):
                        if dp[m+1][j][d] == INF:
                            continue
                        if color_diff[c][d]:
                            new_power = dp[i][m][c] + dp[m+1][j][d]
                            # 更新颜色c和d的情况
                            if new_power > dp[i][j][c]:
                                dp[i][j][c] = new_power
                            if new_power > dp[i][j][d]:
                                dp[i][j][d] = new_power

    # 寻找所有可能的区间中的最大值
    max_val = 0
    for i in range(n):
        for j in range(i, i + n):
            for c in range(1, max_color + 1):
                if dp[i][j][c] > max_val:
                    max_val = dp[i][j][c]
    print(max_val)

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