結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    
    A = list(map(int, input[idx:idx+N]))
    idx += N
    C = list(map(int, input[idx:idx+N]))
    idx += N
    
    # 复制数组以处理环状结构
    A += A[:N]
    C += C[:N]
    
    max_length = 2 * N
    dp = [[{} for _ in range(max_length)] for __ in range(max_length)]
    
    # 初始化区间长度为1
    for i in range(max_length):
        dp[i][i][C[i]] = A[i]
    
    # 处理区间长度从2到N
    for l in range(2, N + 1):
        for i in range(max_length - l + 1):
            j = i + l - 1
            for k in range(i, j):
                # 子区间i到k和k+1到j
                for c1 in dp[i][k]:
                    for c2 in dp[k+1][j]:
                        if abs(c1 - c2) <= K:
                            total = dp[i][k][c1] + dp[k+1][j][c2]
                            # 将total加入i-j区间的颜色c1和c2
                            for color in [c1, c2]:
                                if color not in dp[i][j] or total > dp[i][j].get(color, 0):
                                    dp[i][j][color] = total
    
    # 寻找所有可能的区间i-j的最大值，其中i到j的长度不超过N
    max_val = 0
    for i in range(max_length):
        for j in range(i, min(i + N, max_length)):
            if j - i + 1 > N:
                continue
            current = dp[i][j]
            for c in current:
                if current[c] > max_val:
                    max_val = current[c]
    print(max_val)

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