題目大意：將一段木棒按要求切割，每次切割都要付出與木棒長(zhǎng)度相同的代價(jià)，求最小代價(jià)切割。
狀態(tài)表示：d[x][y]表示[x，y]區(qū)間上切割所用的最小值，轉(zhuǎn)移方程：d[x][y]=min{d[x][a[i]]+d[a[i]][y]+(y-x)|a[i]為[x，y]內(nèi)的切割點(diǎn)}
#include <stdio.h>
#include <string.h>
#define N 55
#define INF 1 << 29
#define MIN(a, b) (a < b ? a : b)
int a[N], c[N][N];
int main()
{
int l, n, d;
while(scanf("%d", &l), l)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
a[0] = 0, a[n + 1] = l;
for(int i = 0; i <= n; i++)
c[i][i + 1] = 0;
for(int i = 1; i <= n + 1; i++)
{
for(int j = i - 2; j >= 0; j--)
{
d = INF;
for(int k = j + 1; k < i; k++)
d = MIN(d, c[j][k] + c[k][i]);
c[j][i] = d + a[i] - a[j];
}
}
printf("The minimum cutting is %d.\n", c[0][n + 1]);
}
return 0;
}