It is easy to notice that different selections in the order of cutting can led to different prices. For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price.

Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.

Input 

The next line consists of n positive numbers c_i ( 0 < c_i < l) representing the places where the cuts have to be done, given in strictly increasing order.

An input case with l = 0 will represent the end of the input.

Output 

Sample Input 

100
3
25 50 75
10
4
4 5 7 8
0

Sample Output 

The minimum cutting is 200.
The minimum cutting is 22.

 状态转移方程：d(i,j)=min(d(i,k)+d(k,j)+a[j]-a[i]) (i<k<j)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn=55;
 7 const int INF=10000000;
 8 int d[maxn][maxn],a[maxn],l,n;
 9 inline int min(int a,int b){return a<b?a:b;}
10 
11 int dp(int i,int j)
12 {
13     if(i+1==j) return d[i][j]=0;
14     if(d[i][j]!=-1) return d[i][j];
15     d[i][j]=INF;
16     for(int k=i+1;k<j;k++)
17         d[i][j]=min(d[i][j],dp(i,k)+dp(k,j)+a[j]-a[i]);
18     return d[i][j];
19 }
20 int main()
21 {
22     while(~scanf("%d",&l),l)
23     {
24         scanf("%d",&n);
25         memset(d,-1,sizeof(d));
26         for(int i=1;i<=n;i++) scanf("%d",a+i);
27         a[0]=0;a[n+1]=l;
28         printf("The minimum cutting is %d.\n",dp(0,n+1));
29     }
30     return 0;
31 }