P5531 [CCO2019] Human Error 题解

可能是一个比较劣的做法。

但复杂度是对的。

思路

我们容易发现状态数非常的稀少。

一个比较宽松的上限时 \(3^{13}\) 种状态

由于每个点每走一步会吃掉一个棋子。

所以实际的状态是远远达不到这个上限。

那么我们可以直接设 \(dp_{i,0/1,0/1}\) 为在 \(i\) 状态下，目前是 Justin 或 Donald 操作，先手赢得概率与后手赢得概率。

转移可以直接把所有后继找出来排序，取前 \(k\) 大即可。

时间复杂度：\(O(Sn^2\log n)\)，\(S\) 为状态数。

Code

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
// #define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for (int i = (x); i <= (y); i++)
#define pre(i, x, y) for (int i = (x); i >= (y); i--)
inline void JYFILE19();

typedef double dbl;
typedef pair<int, int> PII;

bool ST;
const int N = 14;
const int M = 2e6 + 10;
const int mod = 998244353;

int n, m, f[2], ct;
int a[N], id[N][N];
dbl dp[M][2][2];
string s[N];
vector<int> to[N];
int vx[] = {0, 1, 0, -1};
int vy[] = {1, 0, -1, 0};

inline void dfs(int now, int op) {
  vector<dbl> res;
  int a[N]{}, s = now;
  pre(i, ct, 1) a[i] = s % 3, s /= 3;
  fro(i, 1, ct) {
    if (a[i] == op + 1) {
      for (auto j : to[i]) {
        if (a[j]) {
          int x = a[j], y = a[i], nt = 0;
          a[j] = y, a[i] = 0;
          fro(k, 1, ct) nt = nt * 3 + a[k];
          dfs(nt, op ^ 1);
          res.eb(dp[nt][op ^ 1][op]);
          a[j] = x, a[i] = y;
        }
      }
    }
  }
  sort(res.begin(), res.end(), [&](dbl x, dbl y) { return x > y; });
  dbl sum = 0;
  int h = f[op];
  for (auto i : res) {
    if (h == 0) break;
    h--, sum += i;
  }
  if(h != f[op]) dp[now][op][op] = sum / (f[op] - h);
  dp[now][op][op ^ 1] = 1 - dp[now][op][op];
}

signed main() {
  JYFILE19();
  cin >> n >> m;
  fro(i, 1, n) cin >> s[i];
  cin >> f[0] >> f[1];
  fro(i, 1, n) fro(j, 1, m) id[i][j] = ++ct;
  fro(i, 1, n) fro(j, 1, m) fro(k, 0, 3) {
    int x = i + vx[k];
    int y = j + vy[k];
    if (1 <= x && x <= n && 1 <= y && y <= m) {
      to[id[i][j]].eb(id[x][y]);
    }
  }
  ct = 0;
  fro(i, 1, n) {
    fro(j, 1, m) {
      if (s[i][j - 1] == 'J') a[++ct] = 1;
      if (s[i][j - 1] == 'D') a[++ct] = 2;
    }
  }
  int now = 0;
  fro(i, 1, ct) now = now * 3 + a[i];
  dfs(now, 0);
  printf("%.3lf\n", dp[now][0][0]);
  return 0;
}

bool ED;
inline void JYFILE19() {
  // freopen("", "r", stdin);
  // freopen("", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  double MIB = fabs((&ED - &ST) / 1048576.), LIM = 500;
  cerr << "MEMORY: " << MIB << endl, assert(MIB <= LIM);
}