問題
N 個のコンテナを K 個のグループに分ける。cost(i,j) = sum(A[i..j])^2。全グループのコスト合計を最小化。
制約
$1 \le K \le N \le 5000$
$1 \le A_i \le 10^4$
cost が opt 単調性を満たす
入出力例
入力例 1
6 3
1 3 2 5 4 2出力例 1
49ヒント (段階的開示)
ヒント1: 方向性
dp[k][i] = 最初の i 個を k グループに分ける最小コスト。素朴は O(KN^2)。
ヒント2: アプローチ
opt[k][i] が単調なら分割統治で各層 O(N log N)。
ヒント3: 誘導
sum^2 は四辺形不等式 cost(a,c)+cost(b,d) ≤ cost(a,d)+cost(b,c) を満たす。
模範解答 (Python)
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def main():
N, K = map(int, input().split())
A = list(map(int, input().split()))
prefix = [0] * (N + 1)
for i in range(N):
prefix[i+1] = prefix[i] + A[i]
def cost(l, r):
s = prefix[r] - prefix[l-1]
return s * s
INF = float('inf')
dp = [INF] * (N + 1)
dp[0] = 0
for k in range(K):
new_dp = [INF] * (N + 1)
def dc(lo, hi, opt_lo, opt_hi):
if lo > hi:
return
mid = (lo + hi) // 2
best = INF
best_opt = opt_lo
upper = min(opt_hi, mid - 1) if k < K - 1 else min(opt_hi, mid)
for m in range(opt_lo, upper + 1):
if dp[m] == INF:
continue
c = dp[m] + cost(m + 1, mid)
if c < best:
best = c
best_opt = m
new_dp[mid] = best
dc(lo, mid - 1, opt_lo, best_opt)
dc(mid + 1, hi, best_opt, opt_hi)
dc(k + 1, N, k, N - 1)
dp = new_dp
print(dp[N])
main()Step-by-Step 解説
1DP 定式化
$dp[k][i] = \min_{m<i}(dp[k-1][m] + \text{cost}(m+1, i))$。
$dp[k][i] = \min_{m<i}(dp[k-1][m] + \text{cost}(m+1, i))$。
2四辺形不等式
$\text{cost}$ が満たせば opt 単調。
$\text{cost}$ が満たせば opt 単調。
3分割統治
mid の opt を探し、左半分は [opt_lo, best_opt]、右半分は [best_opt, opt_hi]。
mid の opt を探し、左半分は [opt_lo, best_opt]、右半分は [best_opt, opt_hi]。
4計算量
$O(KN \log N)$。
$O(KN \log N)$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 再帰深さ制限 | N=5000 で深い | setrecursionlimit |
| opt_hi の上限 | mid 以上は無意味 | min(opt_hi, mid-1) |
| 四辺形不等式未確認 | 成立しない問題に適用 | 事前に単調性を確認 |
次のステップ
- SMAWK アルゴリズム