題目大意：將一段木棒按要求切割，每次切割都要付出與木棒長度相同的代價，求最小代價切割。
狀態(tài)表示：d[x][y]表示[x，y]區(qū)間上切割所用的最小值
狀態(tài)轉(zhuǎn)移方程：d[x][y]=min{d[x][a[i]]+d[a[i]][y]+(y-x)|a[i]為[x，y]內(nèi)的切割點}
以下是我的代碼：
#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 閱讀(2447)
評論(8) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃