【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d686
【解題想法】區間DP
- a[ ]：題目給定第1～N個切割的地方，且由小到大排列好。
- 加入第0個切割點及第N+1個切割點：
- a[0] = 0
- a[N+1] = L
- dp[x][y]：從第 x 個切割點到第 y 個切割點，所需最小的成本。
- dp[x][x+1] = 0 (中間無其它切割點)
- (Line-13) 枚舉中間的切割點，找出最小成本。
- (Line-15) 需加上a[y] – a[x]
- 【例子】L = 10，三個切割點：2、4、7，a[ ] = {0, 2, 4, 7, 10}|
- 中間只剩一個切割點：抬起這根木棍的成本。
- dp[2][4] = 6
- dp[1][3] = 5
- 中間還有兩個切割點：dp[1][4] = 下面兩個選項中成本最小者，再加上 8 (a[4] – a[1])，抬起這根木棍的成本。
- 先做第 2 個切割點，dp[1][2] + dp[2][4] = 6
- 先做第 3 個切割點，dp[1][3] + dp[3][4] = 5
- 中間只剩一個切割點：抬起這根木棍的成本。
#include <iostream>
#include <cstring>
using namespace std;
int dp[55][55]; //最多50個切割的地方
int a[55]; //第1～N個切割的地方，由小到大排列好。
int solve(int x, int y){
if (~dp[x][y]) return dp[x][y]; //記憶化
if (x+1 == y) return dp[x][y] = 0;
int cost = 0x3F3F3F3F;
for (int i = x+1; i < y; i++){
//枚舉中間的切割點
cost = min(cost, solve(x, i) + solve(i, y));
}
return dp[x][y] = cost + a[y] - a[x];
}
int main() {
int L, N;
while (cin >> L){
if (L == 0) break;
memset(a, 0, sizeof(a));
memset(dp, -1, sizeof(dp));
cin >> N;
for (int i = 1; i <= N; i++){
cin >> a[i];
}
a[N+1] = L;
cout << "The minimum cutting is " << solve(0, N+1) << ".\n";
}
return 0;
}