P2473 [SCOI2008]奖励关

\(P2473\) \([SCOI2008]\)奖励关

令\(f[S,i]\)表示当前吃的状态为\(S\),当前是第\(i\)次抛的按最优决策的期望得分

但由于起始状态是确定的,而终态是不确定的,所以考虑改变定义逆推

令\(f[S,i]\)表示\(1\)到\(i-1\)的状态为\(S\),当前是第\(i\)次抛,还能得到的期望得分

考虑所有抛出的\(k\)

1. \(k\)可吃,可吃可不吃 \(f[i,S] += max(f[i+1,S],f[i+1,S|(1<<k)])\)
2. \(k\)不可吃 \(f[i,S] += f[i+1,S]\)

弄完后要除\(n\)

初始值为\(0\)

答案为\(f[1,0]\)

\(tips:\) 判断一个集合(\(S\))是否是另一个集合(\(T\))的子集

\(S \& T == S\) (即 \(S \cap T == S\)) 则是

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;

template <typename T> void in(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {x = 10*x+ch-'0'; ch = getchar();}
    x *= f;
}

template <typename T> void out(T x) {
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) out(x/10);
    putchar(x%10+'0');
}
//---------------------------------------------------------------

int n,m;
int a[16],need[16];
double f[110][1<<16];

int main() {
    in(m); in(n);
    for(int i = 0;i < n; ++i) {
        in(a[i]); int x;
        while(1) {
            in(x); if(!x) break;
            need[i] |= (1<<(x-1));
        }
    }
    for(int i = m;i >= 1; --i) {
        for(int j = 0;j < (1<<n); ++j) {//debug < (1<<n)  ->  < (1<<n)-1
            for(int k = 0;k < n; ++k) {
                if((j&need[k]) == need[k]) f[i][j] += max(f[i+1][j],f[i+1][j|(1<<k)]+a[k]);
                else f[i][j] += f[i+1][j];
            }
            f[i][j] /= n;
        }
    }
    printf("%.6lf",f[1][0]);
    return 0;
}

P2473 [SCOI2008]奖励关

原文：https://www.cnblogs.com/mzg1805/p/11715344.html