BZOJ 1076 SCOI2008 奖励关期望状压DP

题目大意：给定k次弹出宝物的机会，每次随机弹出n种宝物的机会，如果吃过这种宝物的所有前提宝物就可以吃这种宝物，求最优策略的期望得分

看到数据范围果断状压DP- - 不看数据范围害死人- -

至于吃还是不吃这是个问题

对于这种最优策略的期望DP 我们一般都是从后往前推

枚举每次出现宝物枚举此时的状态枚举宝物是哪种

如果当前的宝物可以吃就在吃与不吃的后继状态中选择最大值加到当前状态上

如果当前的宝物不能吃只能选择不吃的后继状态加到当前状态上

最后输出f[1][0]就是答案

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int k,n,score[20],pre[20]; double f[110][1<<15]; int main() { int i,j,x; cin>>k>>n; for(i=1;i<=n;i++) { scanf("%d",&score[i]); while(scanf("%d",&x),x) pre[i]|=1<

BZOJ 1076 SCOI2008 奖励关 期望状压DP