Felicia

2007年9月4日

[动态规划]pku1170
     摘要: 呼~今天去学校啦！早上7点起床写题，挑了个简单题写 ^_^
这个是IOI95的DP题。用一个b位的6进制数i表示状态。这个6进制数的每一位分别表示相应物品的数量。f[i]表示状态i下的最小花费。同样也可以用6进制数j表示优惠。那么，f[i]就能转移到f[i - j]，如果优惠j可用的话。代价是使用优惠j时减少的花费。最后的答案就是min(f[i])，0 <= i <= start（start是初始状态）。

  阅读全文
posted @ 2007-09-04 08:37 Felicia 阅读(661) | 评论 (0) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia