链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944
题意：
有一根长度为L（L＜1000）的棍子，还有n（n＜50）个切割点的位置（按照从小到大排列）。
你的任务是在这些切割点的位置处把棍子切成n＋1部分，使得总切割费用最小（每次切割的费用等于被切割的木棍长度）。
分析：
设d(i,j)为切割小木棍第i点到第j点的最优费用，则d(i,j) = min{d(i,k) + d(k,j) | i<k<j} + a[j]-a[i]，
其中最后一项a[j]-a[i]代表第一刀的费用。切完之后，小木棍变成i～k和k～j两部分，状态转移方程由此可得。
把切割点编号为1～n，左边界编号为0，右边界编号为n＋1，则答案为d(0,n+1)。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int a[+], d[+][+]; // d[i][j]为切割小木棍第i点到第j点的最优费用 int dp(int L, int R){
if(d[L][R] || L + == R) return d[L][R];
int v = ;
for(int M = L + ; M < R; M++) v = min(v, dp(L, M) + dp(M, R));
return d[L][R] = v + a[R] - a[L];
} int main(){
int L, n;
while(scanf("%d", &L) && L){
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
a[n+] = L;
memset(d, , sizeof(d));
printf("The minimum cutting is %d.\n", dp(, n + ));
}
return ;
}