设为首页 加入收藏

TOP

POJ3292 SpaceElevator [DP]
2015-07-24 05:43:44 来源: 作者: 【 】 浏览:4
Tags:POJ3292 SpaceElevator
题目大意:有一头奶牛要上太空,他有很多种石头,每种石头的高度是hi,但是不能放到ai之上的高度,并且这种石头有ci个
将这些石头叠加起来,问能够达到的最高高度。
解题思路:首先对数据进行升序排序,这样才是一个标准的多重背包的问题
为什么要排序?
因为只有这样才能得到最优解,如果一开始就是高的在前面,那么后面有低的却不能选到,就直接选高的去了。这样是不能达到最优解的
使f[i]的状态标记,是否可以达到这个高度
这样能够达到取f[i]中i的最大值即可。

这里要注意max赋初值的时候要赋值为0,不能为-1,因为答案有可能为0

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; int type; int f[44444],usr[44444]; struct Block { int h,a,c; }block[555]; bool cmp(Block a,Block b) { return a.a
        
         

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇uva:10340 - All in All(字符串.. 下一篇HDU 3488Tour(网络流之最小费用流..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: