心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
题目大意:将一段木棒按要求切割,每次切割都要付出与木棒长度相同的代价,求最小代价切割。
状态表示: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]!=-1return 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==0break;
       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 阅读(2410) 评论(8)  编辑 收藏 引用 所属分类: 题目分类:动态规划

FeedBack:
# re: UVa 10003 Cutting Sticks
2010-06-04 23:58 | YouSuck
This code is very slow and wastes memory a lot.  回复  更多评论
  
# re: UVa 10003 Cutting Sticks
2010-11-17 13:59 | jerrymu1234
请教楼主:

如何在求minimum cost值的同时,
记录所cut的点的次序??被困扰好久。。。。。

比如input:
10 (木棍长)
3 (切3次)
2 4 7 (在2,4,7处切)
Output:
The minimum cost is 20.
The optimal cutting sequence: 4,2,7  回复  更多评论
  
# re: UVa 10003 Cutting Sticks
2010-11-17 21:30 | Lee1R
@jerrymu1234
d[i][j]表示在区间[i,j]上切割所需要的最小值;
f[i][j]表示在区间[i,j]上切割达到最小值时的一个切割点;
则可以根据f[i][j]把区间[i,j]分成两份:[i,f[i][j]]和[f[i][j],j];
这样,对分成的两个区间继续分割,即可得到最优解。
f[i][j]的值只需要在每次更新d[i][j]的时候随着更新即可。  回复  更多评论
  
# re: UVa 10003 Cutting Sticks
2010-11-18 02:56 | jerrymu1234
@Lee1R

感谢楼主回复!

按照你的思路,那么代码是否得重新写,源代码里只有
d[x][y]=min(d[x][y],dp(x,a[i])+dp(a[i],y)+(y-x));
最后直接输出return d[x][y],
如何判断,每次更新的d[i][j]?

但如何在现有代码基础上改动呢?
  回复  更多评论
  
# re: UVa 10003 Cutting Sticks
2010-11-18 14:07 | Lee1R
@jerrymu1234

d[x][y]=min(d[x][y],dp(x,a[i])+dp(a[i],y)+(y-x));
改成:
if(d[x][y]>dp(x,a[i])+dp(a[i],y)+(y-x))
{
d[x][y]=dp(x,a[i])+dp(a[i],y)+(y-x);
f[x][y]=a[i];
}
这样,最终记录的f[x][y]就是d[x][y]达到最优时的切割点。
寻找最优解的时候,需要再写一个递归函数,因为每找到一个切割点就把原区间分成了两份,要对这两份继续递归找相应的切割点。  回复  更多评论
  
# re: UVa 10003 Cutting Sticks
2010-11-18 14:49 | Lee1R
@YouSuck
Thank you for your reminding!I hvae found my fault...

@jerrymu1234
不用谢。我也只有趁这两天的时间用用电脑了。等后天NOIP结束之后,我就要加紧准备保送生考试了,就不能用电脑了。
我上面的代码有很大的瑕疵,一楼已经提出来了。
把d[i][j]定义为“切割第i个切割点到第j个切割点之间的木棒需要的最小值”就只需要50*50的数组了。状态转移方程也需要相应修改。  回复  更多评论
  
# re: UVa 10003 Cutting Sticks[未登录]
2010-11-21 06:57 | 1
请教博主:

博主的意思是在dp函数内部就可以加上
if(d[x][y]>dp(x,a[i])+dp(a[i],y)+(y-x))
{
d[x][y]=dp(x,a[i])+dp(a[i],y)+(y-x);
f[x][y]=a[i];
}

然后再写一个递归函数求f[x][y]里的最优解吗?
这个递归函数应该如何写?  回复  更多评论
  
# re: UVa 10003 Cutting Sticks
2010-11-27 23:52 | Lee1R
@1
请你阅读有关动态规划构建最优解方面的文章。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理