题解：AT_abc314_e [ABC314E] Roulettes

题意

有 台轮盘。第 台轮盘（ ）上写有 个整数 ，每次支付 日元可以玩一次。每玩一次第 台轮盘，会等概率随机选出 到 之间的一个整数 ，获得 分。

每次轮盘获得的分数相互独立。

Takahashi 想要获得至少 分。Takahashi 会采取使得在获得至少 分之前所支付金额尽可能小的策略。并且，Takahashi 每次玩轮盘时，可以根据之前所有轮盘的结果选择下一次要玩的轮盘。

请计算 Takahashi 在获得至少 分之前所支付金额的期望值。

思路

首先显然不是贪心。我们可以想象成，每次得到 到 内的任意一个整数，花费 代价，可以转换成完全背包。

发现正推似乎不太好做。所以我们倒退。设计状态 表示当前离 还有 点积分时的代价期望最小值，显然有 。

考虑转移，我们可以写出转移式：

但是存在 ，无法直接做。可以通过数学手段证明其绝对收敛（不写证明过程了，但确实可行），所以可以将其视为方程来看。最终转移式如下：

其中 。

代码

#include <bits/extc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int MAXN = 1e2 + 10;
const ll INF = 2e18;

struct Roulette {
  int c, p, cnt;
  vector<int> s;
} a[MAXN];

int n, m;
ld dp[MAXN << 1];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].c >> a[i].p;
    a[i].s.assign(a[i].p + 5, 0);
    for (int j = 1; j <= a[i].p; j++) {
      cin >> a[i].s[j];
      a[i].cnt += !a[i].s[j];
    }
  }
  for (int i = m - 1; i >= 0; i--) {
    dp[i] = INF;
    for (int j = 1; j <= n; j++) {
      ld sum = a[j].p * a[j].c;
      for (int k = 1; k <= a[j].p; k++) {
        if (!a[j].s[k]) continue;
        sum += dp[i + a[j].s[k]];
      }
      dp[i] = min(dp[i], sum / (a[j].p - a[j].cnt));
    }
  }
  cout << fixed << setprecision(50) << dp[0];
  return 0;
}