题解 P2473 【[SCOI2008]奖励关】

· · 个人记录

dp想清楚怎么转移再写！！！

开始瞎想了一堆不行的转移还写，然后这个题一共写了2.5h

考虑倒着dp,dp[i][j]表示i轮后状态为j接下来期望获得的收益，这样最后答案就是dp[0][0]

策略就是当前如果吃这个物品（当然前提是能吃），吃完后的期望收益和这个物品的价值的和为正数，即期望获利，就吃，否则不吃

转移：先倒着枚举轮数i，然后枚举状态j、给出的物品k，如果给出的物品能吃而且score[k]+dp[i+1][j|(1<<(k-1))]>0（就是说吃这个物品之后的期望收益和物品价值之和为正数）就吃，否则不吃；

如果吃了，从dp[i+1][j|(1<<(k-1))]转移过来，否则从dp[i+1][j]（而不是0）转移过来！！！