题解 P2473 [SCOI2008] 奖励关

· · 题解

P2473 [SCOI2008] 奖励关 题解

[Statement]

Date: May 5th 2021

前言

一道比较简单的期望状压 dp 题。

分析：

题意转化后，就是要求你在最优策略下的期望得分。(最优策略是指能最大化期望得分策略）

注意到 n \le 15，可以状压当前持有(吃过)物品的状态 S。

我们记录物品 i 的前提集合为 R_i，物品 i 能取当且仅当 R_i \subseteq S，

dp 设计：

显然最优策略和当前持有的物品以及轮数有关，可以考虑利用状压 dp 求解。

如果从前往后转移，会发现问题不满足最优子结构(比如选择一个 p_i 为负的物品当前看起来不优，实际上却能增加之后的期望得分)，当前选择具有后效性。

因此我们无法确定当前的最优策略，不能从前往后 dp。

不过如果我们知道了第 i + 1 轮下，持有物品集合 S 的结果，我们就能确定第 i 轮的最优策略了。

于是我们可以 从后往前 dp，具体的：

不难发现这样 dp 没有后效性，满足最优子结构。当前选与不选某一个物品，并不会对更早的轮次产生影响。

dp 转移：

首先枚举剩余轮数 i 和物品状态 S, 然后枚举此轮抛出 n 种物品的不同情况转移。

当枚举到第 j 个物品时, 分类讨论：

对抛出 n 种物品的不同情况，在各自的最优策略下的未来期望收益取平均值，表示期望收益，作为 dp_{i,S}。(因为抛出每种物品的概率相等，所以期望可以用取平均值表示)

综上，可以将转移表示为：

dp_{i, S} = \frac 1n \sum_{j=1}^n \begin{cases} dp_{i-1, S} & R_j \not \subseteq S\\ p_j + dp_{i-1,S | j} & R_j \subset S \wedge p_j \ge 0\\ \max\{p_j + dp_{i-1, S | j}, dp_{i-1, S} \} & R_j \subseteq S \wedge p_j \lt 0 \end{cases}

答案为 dp_{k, \emptyset}，即还剩 k 轮且没有任何物品时(初始状态)，在最优策略下的未来期望收益。

正确性显然，复杂度 O(k2^nn) 可以接受。

初始化时，令 dp_{1, S} = \frac 1n\sum_{R_j \subseteq S} \max\{p_j, 0\}(或者 dp_{0,S} = 0 也行)。

实现的时候第 2, 3 个转移可以合并，因为 p_j \ge 0 时，一定有 p_j + dp_{i-1, S|j} \ge dp_{i-1, S}。

实际有用的 dp 数组只有 dp_{i} 和 dp_{i-1}，可以滚动数组优化，不过在此题中没有必要。

Code:

#include <bits/stdc++.h>

template<class _Tp = int> _Tp read() {
  _Tp w = 0;
  bool f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) w = (w << 3) + (w << 1) + (ch ^ 48), ch = getchar();
  return f ? -w : w;
}

const int kMaxN = 15, kMaxK = 1e2 + 5;
int n, k;
int R[kMaxN];
int p[kMaxN];
double dp[kMaxK][1 << kMaxN];
int main() {
  k = read(), n = read();
  for (int i = 0, r; i < n; i++) {
    p[i] = read();
    while(r = read())
      R[i] |= 1 << (r - 1);
  }
  for (int i = 1; i <= k; i++)
    for (int S = 0; S < 1 << n; S++) {
      for (int j = 0; j < n; j++)
        if ((R[j] & S) != R[j]) dp[i][S] += dp[i - 1][S];
        else 
          dp[i][S] += std::max(dp[i - 1][S], p[j] + dp[i - 1][S | 1 << j]);
      dp[i][S] /= n;
    }
  printf("%.6lf", dp[k][0]);
  return 0;
}
\mathfrak{The\ End.}