首页 > 其他 > 详细

状压dp Gym - 100676G

时间:2017-03-17 00:29:11      阅读:226      评论:0      收藏:0      [点我收藏+]

http://codeforces.com/gym/100676

 

题目大意:

给你n个科目,m个关系,例如A->B,表示要学习B科目,一定要把A科目学习掉。同理,如果还有C->B,那么,B就要同时学掉A和C才能学B科目。

如果你是第k天学习这个科目,那么你的val += k * W[i],这个i表示你当天学的科目。

问,怎么学习让自己的val最大。

 

思路:状压dp

定义can[i],表示学习第i个科目之前,所需要的学习的集合是啥,然后判断(i & can[j]) == can[j],然后就去转移就好了!

千万别忘了初始化dpTAT(太久没写DP了,都忘了还有初始化了)

状压dp Gym - 100676G

原文:http://www.cnblogs.com/heimao5027/p/6561934.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!