白駿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

同じ方法でデータを探索して最高値を求める過程は同じである.しかし,無意味な繰返し計算を減らすために,dp配列(始点,終点)を用いて計算を行うたびに配列に保存する方式が選択されている.
サイクル再帰関数の過程でdp配列に格納された計算が現れた場合、さらなる計算は行わず、dp配列値を返す.
無意味な繰り返し計算を減らす!