Problem
Source: BZOJ 1076, SCOI 2008
Description
你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出 $k$ 次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。宝物一共有 $n$ 种,系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。也就是说,即使前 $k-1$ 次系统都抛出宝物1(这种情况是有可能出现的,尽管概率非常小),第 $k$ 次抛出各个宝物的概率依然均为 $1/n$。 获取第 $i$ 种宝物将得到 $P_i$ 分,但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $S_i$。只有当 $S_i$ 中所有宝物都至少吃过一次,才能吃第 $i$ 种宝物(如果系统抛出了一个目前不能吃的宝物,相当于白白的损失了一次机会)。注意,$P_i$ 可以是负数,但如果它是很多高分宝物的前提,损失短期利益而吃掉这个负分宝物将获得更大的长期利益。 假设你采取最优策略,平均情况你一共能在奖励关得到多少分值?
数据规模:$1 \leq k \leq 50$,$1 \leq n \leq 15$,分值为 $[-10^6,10^6]$ 内的整数。
Input
第一行为两个正整数 $k$ 和 $n$,即宝物的数量和种类。以下 $n$ 行分别描述一种宝物,其中第一个整数代表分值,随后的整数依次代表该宝物的各个前提宝物(各宝物编号为1到 $n$),以0结尾。
Output
输出一个实数,保留六位小数,即在最优策略下平均情况的得分。
Sample Input
6 6
12 2 3 4 5 0
15 5 0
-2 2 4 5 0
-11 2 5 0
5 0
1 2 4 5 0
Sample Output
10.023470
Solution
$n \leq 15$,所以可以用 15 位的二进制数表示每种物品选或不选。
本轮期望 =(上一轮期望 + 本轮得分)/ n
最优策略的期望动归应该倒推,倒推是有效状态从有效状态推来,无效状态无所谓,因为答案 $f(1,0)$ 是一个有效状态;而顺推则可能从无效状态推到有效状态,不好判断当前状态是否有效。
状态转移方程:
$f(i,j)$:第 $i$ 轮已经收集的宝物集合 $j$ 的期望
$v(k)$:第 $k$ 个宝物的价值
\[f(i,j) += \begin{cases} f(i+1,j) / n & \text{本宝物可以收集}\\ \max \Big ( f(i+1,j), f(i+1,f(i+1, j \mid 1 <<(k-1)) + v[k] \Big ) \Big / n & \text{本宝物不能收集} \end{cases}\]Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
using namespace std;
int v[20], d[20], P[21];
double f[55][65536];
int n, k, t;
void Init() {
scanf("%d%d", &k, &n);
for(int i = 1; i <= n+1; i++) P[i] = 1 << (i - 1);
int x;
for(int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
while(scanf("%d", &x)) {
if(x == 0) break;
d[i] += P[x];
}
}
}
void Dp() {
for(int i = k; i; i--)
for(int j = 0; j <= P[n + 1] - 1; j++) {
f[i][j] = 0;
for(int h = 1; h <= n; h++) {
if ((d[h] & j) == d[h])
f[i][j] += max(f[i + 1][j], f[i + 1][j | P[h]] + v[h]);
else f[i][j] += f[i + 1][j];
}
f[i][j] /= double(n);
}
printf("%.6lf", f[1][0]);
}
int main() {
Init();
Dp();
return 0;
}