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]);
}