切割能量棒

题目链接：http://www.razxhoi.com/mod/programming/view.php?id=5450
【题目描述】切割能量棒(CuttingSticks.cpp/c/pas) uva10003
太空梯需要不同长度的能量棒，你的任务是切割能量棒。切割能量棒的成本是根据能量棒的长度而定。而且切割能量棒的时候每次只切一段。

很显然的，不同切割的顺序会有不同的成本。例如：有一根长10米的能量棒必须在第2、4、7公尺的地方切割。这个时候就有几种选择了。你可以选择先切2米的地方，然后切4米的地方，最后切7米的地方。这样的选择其成本为：10+8+6=24。因为第一次切时能量棒长10米，第二次切时能量棒长8米，第三次切时能量棒长6米。但是如果你选择先切4米的地方，然后切2米的地方，最后切7米的地方，其成本为：10+4+6=20，这成本就是一个较好的选择。　

请找出切割一能量棒所需最小的成本。

【输入格式】

每组测试数据3行，第一行有1个整数L （L<1000），代表需要切割的能量棒的长度。
第二行有一个整数N（N<50），代表需要切的次数。
第三行有N个正整数Ci（0 < Ci < L）代表能量棒需被切割的地方。这N个整数均不相同，且由小到大排列好。
L=0代表输入结束。

【输出格式】
对每一组测试数据，输出最小的切割成本。

【输入样例】
100
3
25 50 75
10
4
4 5 7 8
0

【输出样例】
The minimum cutting is 200.
The minimum cutting is 22.

题解：这道题和合并果子是一个类型的题目，不同的是，这道题中i到i+k中从j（i<j<i+k）切开的花费为f[i][j]+f[j][i+k]+a[i+k]-a[i]，所以动态转移方程为f[i][i+k]=min(f[i][i+k],f[i][j]+f[j][i+k]+a[i+k]-a[i]);

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int l,n,a[105],f[105][105],sum[105];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    freopen("CuttingSticks.in","r",stdin);
    freopen("CuttingSticks.out","w",stdout);
    int i,j,k;
    while(cin>>l&&l!=0)
    {
        memset(a,0,sizeof(a));
        memset(f,127/3,sizeof(f));
        cin>>n;
        a[0]=0;
        a[n+1]=l;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(i=0;i<=n;i++)
        {
            f[i][i+1]=0;
        }
        for(k=2;k<=n+1;k++)
        {
            for(i=0;i<=n-k+1;i++)
            {
                for(j=i+1;j<i+k;j++)
                {
                    f[i][i+k]=min(f[i][i+k],f[i][j]+f[j][i+k]+a[i+k]-a[i]);//作差后加上所要的成本。
                }
            }
        }
        printf("The minimum cutting is %d.\n",f[0][n+1]);
    }
    return 0;
}