題目意思： 有一根長度為l的木棍，木棍上面有m個切割點，每一次切割都要付出當前木棍長度的代價，問怎樣切割有最小代價
解題思路： 1 區間DP
2 區間動態規劃問題一般都是考慮，對於每段區間，他們的最優值都是由幾段更小區間的最優值得到，是分治思想的一種應用，將一個區間問題不斷劃分為更小的區間直至一個元素組成的區間，枚舉他們的組合，求合並後的最優值。
3 設F[i,j]（1<=i<=j<=n）表示區間[i,j]內的數字相加的最小代價 ， 最小區間F[i,i]=0（一個數字無法合並，∴代價為0）每次用變量k（i<=k<=j-1）將區間分為[i,k]和[k+1,j]兩段
4《區間DP模板，代碼》
for(intp = 1 ; p <= n ; p++){//p是區間的長度，作為階段
for(int i = 1 ; i <= n ; i++){//i是窮舉區間的起點
int j = i+p-1;//j為區間的終點
for(int k = i ; k < j ; k++)//狀態轉移
dp[i][j] = min{dp[i][k]+dp[k+1][j]+w[i][j]};//這個是看題目意思，有的是要從k開始不是k+1
dp[i][j]= max{dp[i][k]+dp[k+1][j]+w[i][j]};
}
}
5 對於這一題，如果我們只對最左邊的切割點到最右邊的切割點進行DP，那麼得到的答案肯定是錯的，因為不是整個區間，所以我們必須在木棍的做左邊和左右邊分別增加一個點，那麼得到的就是整個區間，再對這個區間進行DP求解即可
代碼：
[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <set>
using namespace std;
#define MAXN 55
int len , m;
int dp[MAXN][MAXN];
int cut[MAXN];//記錄切割點
void solve(){
int i , j , k , p , tmp , min;
cut[0] = 0 ; cut[m+1] = len;//增加切點，那麼切點有0-m+1
memset(dp , 0 , sizeof(dp));
for(p = 1 ; p <= m+1 ; p++){//區間長度0-m+1
for(i = 0 ; i <= m+1-p ; i++){//區間起點0-m+1-p
j = i+p ; min = 999999999;//j為終點
for(k = i+1 ; k < j ; k++){//枚舉k
tmp = dp[i][k]+dp[k][j]+cut[j]-cut[i];//這個地方注意不是從k+1開始
if(tmp < min) min = tmp;//更新min
}
if(min != 999999999) dp[i][j] = min;//如果min有更新過則賦值給dp[i][j]
}
} www.2cto.com
printf("The minimum cutting is %d.\n" , dp[0][m+1]);//答案就是0-m+1這個區間
}
int main(){
//freopen("input.txt" , "r" , stdin);
while(scanf("%d" , &len) && len){
scanf("%d" , &m);
for(int i = 1 ; i <= m ; i++) scanf("%d" , &cut[i]);
solve();
}
return 0;
}
作者：cgl1079743846
