BZOJ 1076 「SCOI2008」奖励关

这个题挺有趣的啊，感觉其实似乎并不难想，只要能注意到倒推这一点。

看到 n≤15，肯定会想到设 fi,S 表示第 i 次持有 S 集合内的宝物，这 i 次的最大期望分数。
然而会发现没法知道状态是否合法。

于是考虑倒推，设 fi,S 表示第 i 次前持有 S 集合内的宝物，第 i…k 次的最大期望分数。
有转移 fi,S=1nn∑j=1max(fi+1,S,[Si⊆S](fi+1,S⋃{j}+Pj)−[Si⊈S]∞)

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int K = 100;
const int N = 15;
int k,n,full,a[N + 5],s[N + 5];
double f[K + 5][(1 << N) + 5];
int main()
{
    scanf("%d%d",&k,&n),full = (1 << n) - 1;
    for(register int i = 1;i <= n;++i)
    {
        scanf("%d",a + i);
        for(int x = 1;x;)
            scanf("%d",&x),x && (s[i] |= (1 << x - 1));
    }
    for(register int i = k;i;--i)
        for(register int j = 0;j <= full;++j)
        {
            for(register int l = 1;l <= n;++l)
                (s[l] & j) == s[l] ? (f[i][j] += max(f[i + 1][j],f[i + 1][j | (1 << l - 1)] + a[l])) : (f[i][j] += f[i + 1][j]);
            f[i][j] /= n;
        }
    printf("%.6f\n",f[1][0]);
}