Luogu P2473

bzoj 1076

思路

设$f[i][S]$为第$1$个到第$i-1$个吃了的奖励的集合为$S$时，第$i$个到第$K$个的收益为$f[i][S]$

枚举当前出现的第$i$个奖励的种类$j$，若可以食用

$$f[i][S]=f[i][S]+\max\{f[i+1][S], f[i+1][S|1<<(j-1)]+P_j\}$$

若不可以食用

$$f[i][S]=f[i][S]+f[i+1][S]$$

代码

#include <iostream>
#include <cstdio>

int P[16], pre[16], n, K;
double f[110][1<<16];

int main(){
    scanf("%d%d", &K, &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &P[i]);
        int x;
        while(1){
            scanf("%d", &x);
            if(!x) break;
            pre[i]|=1<<(x-1);
        }
    }
    for(int i=K; i; i--)
        for(int j=1; j<=n; j++)
            for(int S=0; S<(1<<n); S++){
                if((S&pre[j])==pre[j])
                    f[i][S]+=std::max(f[i+1][S], f[i+1][S|(1<<(j-1))]+P[j])/n;
                else
                    f[i][S]+=f[i+1][S]/n;	
            }
    printf("%.6lf", f[1][0]);
    return 0;
}