dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

[hdu3236] Gift Hunting

(转自自己的CSDN博客)

一、题目描述

原题地址: http://acm.hdu.edu.cn/showproblem.php?pid=3236

GG有两张奖券,面额分别为V1、V2,准备给MM买礼物。当天是MM生日,所以MM还可以免费得到一份礼物。

礼物有价格和幸福值两个参数,并且礼物分为特殊礼物和普通礼物,特殊礼物是一定要全部到手的。

两张奖券不可以合并使用,、一种礼物也只能买一次。

问MM最大幸福值是多少,如果特殊礼物不能全部得到MM会不高兴,幸福值为-1。

二、题目分析

    比普通的二维背包问题多了两个设置,第一是MM可以免费得到一份礼物,第二是礼物分为特殊和普通两种。

1、特殊礼物是必买齐的,不管幸福值多少,所以要特殊处理一下。

2、用普通背包方法处理普通礼物。

3、由于还可以免费得到一份礼物,还需要一些小处理。

    用f[v1][v2][s]表示奖券V1,V2分别使用v1,v2时,且状态为s时候(s=1表示已经免费得到一份礼物了,s=0表示还木有免费得到礼物),MM的幸福值。

    对于普通礼物,状态转移方程:

f[v1][v2][1] = max( f[v1][v2][1], f[v1][v2][0] + Normal[k].happiness )

f[v1][v2][0] = max( f[v1][v2][0], f[v1 - Normal[k].price][v2][0] + Normal[k].happiness, f[v1][v2 - Norma[k].price][0] + Normal[k].happiness)

    对于特殊礼物,就是直接往里头一个一个礼物塞了。


代码:

hdu3236



写在最后:

个人感觉这应该是非常经典非常基础的二维背包的一个小小拓展,思路上来说还是比较简单的,不过DP写起来还是有一些需要注意的,譬如初始化、边界判断、还有避免物品重复获得某些变量应该用downto而不是to。

还有可以优化之处,譬如v1和v2其实不需要都从V1、 V2开始逆循环,可以设置Max_V1, Max_V2表示截止到上一个礼物最多使用V1和V2中的多少,然后v1和v2从Max_V1, Max_V2开始循环到0。
 

posted on 2010-08-26 20:47 Dango 阅读(292) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理