奖励关

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

Sample Output

10.023470

Solution

$n \leq 15$，所以可以用 15 位的二进制数表示每种物品选或不选。

本轮期望＝（上一轮期望 + 本轮得分）/ ｎ

最优策略的期望动归应该倒推，倒推是有效状态从有效状态推来，无效状态无所谓，因为答案 $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

Github (C++)

#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;
}

PREVIOUSPrint Article

NEXTLandscaping