学步园

/**//**************************************
Problem: UVA 10003 Cutting Sticks
Time: 0.220 s 
Accepted Time: 2009-04-13 11:30:49
Tips: http://blog.csdn.net/biran007/archive/2009/02/06/3865350.aspx
**************************************/
#include <stdio.h>
#include <string.h>
#define MAX 100
int table[MAX][MAX];
int main()
{
    int l; 
    while(1)
    {
        scanf("%d",&l);
        if(l==0)break;
        int n,i,j,k,a[MAX],min,t;
        scanf("%d",&n);
        for(i=1;i<=n;i++)scanf("%d",&a[i]);
        a[0]=0;a[n+1]=l;
        for(i=0;i<=n;i++)table[i][i+1]=0;
        for(i=2;i<=n+1;i++)
        {
            for(j=0;i+j<=n+1;j++)
            {
                min=100000;
                for(k=j+1;k<j+i;k++)
                    if(min>table[j][k]+table[k][j+i])
                        min=table[j][k]+table[k][j+i];
                table[j][i+j]=min+a[j+i]-a[j];
            }
        }    
        printf("The minimum cutting is %d.\n",table[0][n+1]);
    }
    return 0;
}