alan23273850 的刷題筆記
d686: 10003 - Cutting Sticks
Tags: dp
出處：https://zerojudge.tw/ShowProblem?problemid=d686
提交：https://zerojudge.tw/Submissions?problemid=d686&account=allllllan123456
問題：給定一根長度為 $L\in[1,1000]$ 的木棍，以及 $N\in[0,49]$ 個欲切割點 $C_i\in[1,L-1]$，定義每切一刀的成本就是該子木棍在切割之前當下的長度，請問怎樣的切割順序才能有最小的總切割成本？
解法：這題是聖經本 Introduction to Algorithms 第三版裡面第 15.1 的經典章節。對於一根有 n 個可切割點 cut[1:n] 的木棍 (注意 cut[0] 與 cut[n+1] 是為端點)，我們想從中挑一個最好的切割點 j，使得對 A[1:j] 作切割的成本 X 與對 A[j:n] 作切割的成本 Y 之總和 X + Y 要最小。和 c112 不同，因為無論以誰為切割點，整根木棍的長度成本都會算進去，所以它不會成為選擇的理由。另外，因為每個子問題都會被檢查到，所以這題其實可以使用 bottom up 的 DP。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int L, N, cost[52][52], cut[52];
6 for (int i=0; i<=50; i++) cost[i][i+1] = 0;
7 while (cin>>L && L) { cin >> N; cut[0] = 0;
8 for (int i=1; i<=N; i++) cin >> cut[i];
9 cut[N+1] = L;
10 for (int d=2; d<=N+1; d++)
11 for (int i=0; i+d<=N+1; i++) {
12 cost[i][i+d] = INT_MAX;
13 for (int j=i+1; j<i+d; j++) {
14 int temp = cost[i][j] + cost[j][i+d];
15 if (temp < cost[i][i+d]) cost[i][i+d] = temp;
16 }
17 cost[i][i+d] += cut[i+d] - cut[i];
18 }
19 cout << "The minimum cutting is " << cost[0][N+1] << ".\n";
20 }
21 return 0;
22}