题目大意：有一根长l的木棍，有n个切割点要把这根木棍切成n+1段，知道n个切割点的位置。切割一段长度为d的木棍需要的花费为d，如一段长度为10的木棍，有3个切割点：2，5，7，如果按切割点位置从左到右进行切割，所需花费为10+8+5。找出合理的切割顺序使得花费最小。
思路：想明白了就知道是一个很简单的区间DP，这个题刚拿到可能会觉得是贪心把。。。可是在区间dp专题里。。一开始正着想，怎么也找不出状态转移，每一段都与别的区间有关。。这个可以倒着想，这一段切成两端，费用是这根木棍的长度，那么把这两块拼成一根木棍，他们的价值不就是这两根木棍总和吗，这样三块，四块，五块，就都可以由小的区间来了。。。我做过类似的题。。可是为什么想不到呢，一直正着想。。。比如 奶牛产品最优值，穿衣服脱衣服的。。。都是让他从区间是0开始。。从总的没法入手的。。
注意两点；
1.这个只是切的顺序不一样，但是木块的位置不要变，有些用优先队列写得会wa
2.题目告诉你的都是从中间切的，我们可以自行加上从起点（0）终点（l）的切点，所以就是dp[0][n+1]是整根长度的值，而不是dp[1][n]
区间DP，通常都要倒着想，“从无到有”，拆成几部分的，变成合成几部分的。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 55;
int l, n, dp[maxn][maxn], a[maxn],cost[maxn][maxn];
int main()
{
while(~scanf("%d", &l), l)
{
memset(dp, 0x3f3f3f3f, sizeof(dp));
memset(cost, 0, sizeof(cost));
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
dp[n][n+1] = 0;
a[n+1] = l;
a[0] = 0;
sort(a+1, a+n+1);
for(int i = 0; i <= n; i++)
dp[i][i+1] = 0;
for(int len = 2; len <= n+1; len++)
for(int i = 0; i + len <= n+1; i++)
{
int j = i + len;
for(int k = i+1; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+a[j]-a[i]);
}
printf("The minimum cutting is %d.\n", dp[0][n+1]);
}
return 0;
}