問題
$N$ 個の石が一列に並んでいる。隣接する重さ $a, b$ の石を合体させるコストは $a+b$。全ての石を1つに合体させる最小コストを求めよ。
制約
$1 \le N \le 3000$
$1 \le w_i \le 10^6$
入出力例
入力例 1
5
3 4 2 6 1出力例 1
40ヒント (段階的開示)
ヒント1: 方向性
区間DP: $dp[i][j]$ = 石 $i \sim j$ を1つにする最小コスト。素朴は $O(N^3)$ で TLE。Knuth最適化で $O(N^2)$ に。
ヒント2: アプローチ
四辺形不等式を満たす場合: $opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$。最適分割点が単調なので探索範囲を制限。
ヒント3: 誘導
for length in range(2, N+1):
for i in range(1, N-length+2):
j = i + length - 1
lo = opt[i][j-1]
hi = opt[i+1][j]
for k in range(lo, hi+1):
...模範解答 (Python)
import sys
input = sys.stdin.readline
def main():
N = int(input())
w = list(map(int, input().split()))
S = [0] * (N + 1)
for i in range(N):
S[i+1] = S[i] + w[i]
def range_sum(l, r):
return S[r] - S[l-1]
INF = float('inf')
dp = [[INF] * (N + 2) for _ in range(N + 2)]
opt = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(1, N + 1):
dp[i][i] = 0
opt[i][i] = i
for length in range(2, N + 1):
for i in range(1, N - length + 2):
j = i + length - 1
lo = opt[i][j-1]
hi = opt[i+1][j] if j <= N else j - 1
best = INF
best_k = lo
for k in range(lo, min(hi, j-1) + 1):
cost = dp[i][k] + dp[k+1][j] + range_sum(i, j)
if cost < best:
best = cost
best_k = k
dp[i][j] = best
opt[i][j] = best_k
print(dp[1][N])
main()Step-by-Step 解説
1基本の区間DP
$dp[i][j]$ = 区間 $[i,j]$ を1石にする最小コスト。$[i,k]$ と $[k+1,j]$ に分割。
$dp[i][j]$ = 区間 $[i,j]$ を1石にする最小コスト。$[i,k]$ と $[k+1,j]$ に分割。
2四辺形不等式
$w(i,j)$ が四辺形不等式を満たすとき、最適分割点も単調。今回の区間和は凸で成立。
$w(i,j)$ が四辺形不等式を満たすとき、最適分割点も単調。今回の区間和は凸で成立。
3Knuth最適化の核心
$opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$。区間を1つ拡張したとき、最適分割点は縮んだ方向に動かない。
$opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$。区間を1つ拡張したとき、最適分割点は縮んだ方向に動かない。
4計算量の証明
全 $(i,j)$ で探索する $k$ の幅の合計 = $O(N^2)$。
全 $(i,j)$ で探索する $k$ の幅の合計 = $O(N^2)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
opt[i+1][j] が j を超える | 境界チェック漏れ | min(hi, j-1) で上限制限 |
| 四辺形不等式の確認なし | 最適化が適用できない問題に使う | 重み関数が凸かどうか確認 |
| 区間長のループ順序を間違える | 依存関係が壊れる | length = 2, 3, ..., N の順 |
次のステップ
- 発展: 行列チェーン積 $N \le 10^4$
- 最適二分探索木
- Concave SMAWK / Divide & Conquer DP との使い分け