uva10003 Cutting Sticks解题报告

原 作者 张续 | 发表于 | 分类于 2012级

10003 - Cutting Sticks

Time limit: 3.000 seconds

You have to cut a wood stick into pieces. The most affordable company, TheAnalog Cutting Machinery, Inc. (ACM), charges money according to the length ofthe stick being cut. Their procedure of work requires that they only make onecut at a time.

It is easy to notice that different selections in the order ofcutting can led to different prices. For example, consider a stick of length 10meters that has to be cut at 2, 4 and 7 meters from one end. There are severalchoices. One can be cutting first at 2, then at 4, then at 7. This leads to aprice of 10 + 8 + 6 = 24 because the first stick was of 10 meters, theresulting 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 isa better price.

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

input

The input will consist of several input cases. The firstline of each test case will contain a positive number l that represents thelength of the stick to be cut. You can assume l < 1000. The next line willcontain the number n ( n < 50) of cuts to be made.

The next line consistsof n positive numbers ci (0 <ci <l) representing the places where thecuts have to be done, given in strictly increasing order.

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

output

You have to print the cost of theoptimal solution of the cutting problem, that is the minimum cost of cuttingthe given stick. Format the output as shown below.

Sample Input

Sample output

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

Sample Output 

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


uva上的首次1A.
题目大意:
把一根长为l(1<l<1000)的木棒，分成n(1<n<50)段,描述为从最开始的左端到右端的距离，每一次分时所需的花费为当前木块长度.


举个例子.


对一根长度为10米的棍子,需要在离一端2,4,7的地方分割.可以第一次在2,米处，接下来在4,米处，接下来在7米处分割,代价是10+8+6=24;


因为一开始棍子长度是10米，切割后长度为8米，在此切割是6米.


另一种方法是,在4米处切割，然后2米，然后7米这样的价格是10+4+6+20.bi




如图所示的分割.


我的想法.


要求白长度为l，的绳子分为n次（描述是从绳子的最左边的距离由小到大的n个数，分别代表分的位置），每一次分代价是当前长度.


那么最后分完n次之后， 



 

 
，共产生了n-1端绳子,每段绳子的长度都可由该段前后分割点求出.

 
例子的分完后n+1段绳子的长度分别为.

 
2,2,,3,3.(最后一段是由总长度-最后一次分割位置)

 
设想如果是把n+1段绳子拼会到完成的一根绳子,注意他们的位置不能移动只能与左右相邻的某一段组成一段.

 
且代价是产生中间产生的新的绳子长度+每个使用的当前绳子（产生的代价）

 
最短的n+1,段绳子是直接存在的因此产生他们所用代价为0.

 
举个例子，加入原来有10，米长的绳子，在2,5,处分割.

 
分割完之后,所有的3段绳子长度分别是2,3,5.

 
dp[i][j]代表从i号绳子到j号绳子组成一根后所需代价

 
a[i][j]编号为i,到编号为j的绳子合成一根绳子总长度.

 
a[1][1]=2;

 
a[2][2]=3;

 
a[3][3]=5;

 
a[1][2]=5;

 
a[2][3]=8

 
a[1][3]=10;

 
dp[1][1]=dp[2][2]=dp[3][3]=0;

 
dp[1][2]=dp[1][1]+dp[2][2]+a[1][2]=5;

 
dp[2][3]=dp[2][2]+dp[3][3]+a[2][3]=8;

 
dp[1][3]=min(dp[1][2]+dp[3][3]+a[1][3],dp[2][3]+dp[1][1]+a[1][3])=15;

 

 

 

 

 
#include <stdio.h>
#include <string.h>
int dp[101][101]={-1};
int ax[101][101]={0};
int min(int x,int y){
	return x<y?x:y;
}
int slove(int l,int r){
	int i,d,j;
	memset(dp,0,sizeof(dp));
	for(d=0;d<=r;d++){
		for(i=l;i+d<=r;i++){
			for(j=i;j+1<=i+d;j++){
				ax[i][i+d]=ax[i][j]+ax[j+1][i+d];
				if(dp[i][i+d]==0){
					dp[i][i+d]=dp[i][j]+dp[j+1][i+d]+ax[i][i+d];
				}else{
					if(dp[i][i+d]>dp[i][j]+dp[j+1][i+d]+ax[i][i+d]){
						dp[i][i+d]=dp[i][j]+dp[j+1][i+d]+ax[i][i+d];
					}
				}
			}
		}
	}
	return dp[l][r];
}
int main(){
	int n,i,t,l;
	while(scanf("%d",&l)&&l){
		scanf("%d",&n);
		n+=1;
		memset(ax,0,sizeof(ax));
		for(i=1,t=0;i<n;i++){
	      		int x;
	      		scanf("%d",&x);
	     		ax[i][i]=x-t;
	      		t=x;
		}
		ax[i][i]=l-t;
		printf("The minimum cutting is %d.\n",slove(1,n));
	}
	return 0;
}