UVA Cutting Sticks(10003)

题目大意：

        此题大意就是切棍子，若切长度为10的棍子，就得开销10，切长度为8的棍子，开销为8，问根据给定切的位置，如何切能使开销最小。

比如一根棍子原始长度为10，则给定切的位置为2，4，8，则若第一次在2处切，需要开销10，因为切的时候棍子长度为10，切好后产生两个棍子，长度分别为2和8，第二次切若为4，则开销为8，因为4的位置在长度为8的棍子上，第三次切的位置为8，则开销为6，所以最后总的开销为24。但是不同切法，总开销不同，求最小的开销。

 

分析：

        动态规划问题，存在子问题最优解，使用递归即可。将长度为10的棍子看成一个问题，比如若在4处切，则它可以看成1-4棍子的最优解加上4-10棍子的最优解再加上切4时的开销，即

             result =  dfs(x, 4) + dfs(4, y) + c[y] - c[x];   （状态转移方程）

c[y]-c[x]是切4时的开销，dfs(x, 4)是x-4的最优解，dfs(4, y)是4-y的最优解。

 

代码如下：

#include <iostream>
using namespace std;

int dp[55][55], c[55];

int dfs( int x, int y );
int main()
{
	int L;
	int n;
	while(cin>>L,L)
	{
		cin>>n;
		c[0] = 0;
		for( int i = 1; i <= n; i++ )
		{
			cin>>c[i];
		}
		c[n+1] = L;
		memset (dp, -1, sizeof(dp)); 
		for (int i = 0; i <= n; i++)  
            dp[i][i+1] = 0; 
		
		cout << "The minimum cutting is " << dfs(0, n+1) << "." << endl;  
	}
	return 0;
}

int dfs( int x, int y )
{
	if( dp[x][y] > -1 )
		return dp[x][y];
	int result = -1;

	for( int i = x+1; i < y; i++ )
	{
		int temp = dfs(x,i) + dfs(i,y) + c[y] - c[x];   //计算x-i中切割的最小开销 + 计算i-y中切割的最小开销 + 当前在切割i时需要的开销为c[y] - c[x]；
		if( result < 0 || temp < result )  
			result = temp;
	}
	return (dp[x][y] = result);   //将在x-y中切割所需的开销赋给dp[x][y]
}