BZOJ 1076 「SCOI2008」奖励关

发表于 | 分类于 |

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

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

于是考虑倒推，设 \(f_{i,S}\) 表示第 \(i\) 次前持有 \(S\) 集合内的宝物，第 \(i\ldots k\) 次的最大期望分数。
有转移 \[ f_{i,S} = \frac1n \sum\limits_{j=1}^n \max(f_{i+1,S},[S_i \subseteq S](f_{i+1,S\bigcup\{j\}}+P_j)-[S_i \not \subseteq S]\infty) \]

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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]);
}