首页 > 代码库 > 状压dp Gym - 100676G

状压dp Gym - 100676G

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