题目大意：将一段木棒按要求切割，每次切割都要付出与木棒长度相同的代价，求最小代价切割。
状态表示：d[x][y]表示[x，y]区间上切割所用的最小值
状态转移方程：d[x][y]=min{d[x][a[i]]+d[a[i]][y]+(y-x)|a[i]为[x，y]内的切割点}
以下是我的代码：
#include<stdio.h>
const long maxn=57,maxl=1007,INF=2000007;
long l,n,a[maxn],d[maxl][maxl];
long min(long a,long b)
{
return (a<b?a:b);
}
long dp(long x,long y)
{
bool find=false;
if(d[x][y]!=-1) return d[x][y];
d[x][y]=INF;
for(long i=1;i<=n;i++)
if(a[i]>x&&a[i]<y)
{
find=true;
d[x][y]=min(d[x][y],dp(x,a[i])+dp(a[i],y)+(y-x));
}
if(!find) d[x][y]=0;
return d[x][y];
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%ld",&l)==1)
{
if(l==0) break;
scanf("%ld",&n);
for(long i=1;i<=n;i++) scanf("%ld",&a[i]);
// Input
for(long i=0;i<=l;i++)
for(long j=0;j<=l;j++)
d[i][j]=-1;
// Init
dp(0,l);
printf("The minimum cutting is %ld.\n",d[0][l]);
}
return 0;
}
posted on 2010-02-08 16:31
lee1r 阅读(2432)
评论(8) 编辑 收藏 引用 所属分类:
题目分类：动态规划