奖励关（概率dp+状压）

P2473 [SCOI2008] 奖励关 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

概率dp题，因为最多只有15个物品，考虑状压。

设f[i][j]为已进行了i-1次选择，状态为j，采用最优策略的期望值。

进行第i次选择时，每个物品等概率出现。

枚举每个物品z，当前物品可取时，f[i][j]+=max(f[i+1][j|(1<<(z-1))]+w[z],f[i+1][j])/n;

不可取时 f[i][j]+=f[i+1][j]/n;

最后答案为f[1][0];

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int N=1e5+100;
const int MAX=1e9;
double  f[110][1<<15];
int n,k;

int w[110];
int v[110];
int main(){
    cin>>k>>n;
   for(int i=1;i<=n;i++){
       cin>>w[i];
       int x;
       while(cin>>x&&x){
          v[i]=v[i]|(1<<(x-1));    
   }
}
int ww=1<<n;
 for(int i=k;i>=1;i--){
  for(int j=0;j<ww;j++){
    for(int z=1;z<=n;z++) {
      if((j&v[z])==v[z])
      f[i][j]+=max(f[i+1][j|(1<<(z-1))]+w[z],f[i+1][j])/n;
      else f[i][j]+=f[i+1][j]/n;     
    }
  }           
 }
  printf("%.6lf\n",f[1][0]);
 
 
 
    return 0;
}