UVA 10003 切木棍（区间dp）

思路：本题是一个区间dp题，状态方程dp(i,j)=max(dp(i,k)+dp(k,j)+v[j]-v[i]) 其中(i<k<j) ，dp表示从i到j的最小花费。

AC代码：

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define INF 2147483647const int maxn=50+5;int v[maxn];int dp[maxn][maxn];int main(){	int n,l;	while(scanf("%d",&l)==1 && l){		scanf("%d",&n);		for(int i=1;i<=n;i++)		 scanf("%d",&v[i]);		 		v[0]=0;		v[n+1]=l;				memset(dp,0,sizeof(dp));		for(int len=3;len<=n+2;len++) 		  for(int i=0;i<n+2-len+1;i++){		  	int j=i+len-1;		  	dp[i][j]=INF;		  	for(int k=i+1;k<j;k++){		  		dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+v[j]-v[i]);			  }		  }		  		  PRintf("The minimum cutting is %d./n",dp[0][n+1]);	}	return 0;}