白駿11066号ファイルのマージ

白駿11066号ファイルのマージ

コード#コード#

import sys

def dynamic(start, end):
  if dp[start][end] != 0:
    return dp[start][end]
  
  if start == end:
    cost = files[start]
    dp[start][end] = cost
    return cost

  prev_sum = 0
  cost = float('inf')
  for i in range(start, end+1):
    prev_sum += files[i]

  for v in range(start, end):
    cost = min(cost, prev_sum + dynamic(start, v) + dynamic(v+1, end))

  dp[start][end] = cost
  return cost

T = int(sys.stdin.readline())
result = []
dp = [[0 for _ in range(T)] for _ in range(T)]

for i in range(T):
  K = int(sys.stdin.readline())
  files = list(map(int,sys.stdin.readline().split()))
  dp = [[0 for _ in range(K)] for _ in range(K+1)]
  cost = float('inf')

  for v in range(K):
    cost = min(cost, dynamic(0, v) + dynamic(v+1, K-1)) 
  result.append(cost)
  
for r in result:
  print(r)

トラブルシューティング

探索する

DP