BZOJ5248 [多省联考2018] 一双木棋

2018 年 04 月 8 日发布.

Description

有一个 $n \times m$ 的方格， Alice 和 Bob 玩游戏。每次每人可以选择一个格子占领，前提是这个格子未被占领且它左上方的所有格子都已被占领。

第 $i$ 行第 $j$ 列的格子若被 Alice 占领则 Alice 获得 $A_{i, j}$ 分，若被 Bob 占领则 Bob 获得 $B_{i, j}$ 分。 Alice 先手，所有格子都被占领时结束。双方都想最大化自己的得分与对方得分的差。求双方采取最优策略时 Alice 得分与 Bob 得分的差。

$n, m\leqslant10$ 。

Solution

首先显然可以爆搜。就是说每次枚举所有的走法，然后如果这步是 Alice 则取得分差的 max ，否则取 min 。

然后记忆化一下（扔个 map 什么的），这题就过了。

为什么呢？

考虑游戏状态。显然第 i 行选了第一个开始的连续若干个。假设第 $i$ 行选了 $a_i$ 个，那么肯定有 $m \ge a_1 \ge a_2 \ge \dots \ge a_n \ge 0$ 。而且剩余的游戏状态由所有 $a$ 唯一决定。

我们令 $ x_0 = m - a_1, x_1 = a_1 - a_2, x_2 = a_2 - a_3, ..., x_n = a_n $ ，那么所有 $x$ 非负。状态数就是 $\sum_{i=0}^n x_i = m$ 的非负整数解数，利用隔板法可知方案数为 $n + m \choose m$ 。极限数据下不到 2e5 。

Code

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <map>

inline int readInt() {
  int ans = 0, c;
  while (!isdigit(c = getchar()));
  do ans = ans * 10 + c - '0';
  while (isdigit(c = getchar()));
  return ans;
}

const int N = 11;
const int T = 200000;
const int INF = 0x3fffffff;

typedef long long LL;

int n, m;
int A[N][N], B[N][N];

struct State{
  int A[N];
};

LL encode(const State &s) {
  LL ans = 0;
  for (int i = m - 1; i >= 0; --i)
    ans = ans * (n + 1) + s.A[i];
  return ans;
}

State decode(LL x) {
  State s;
  for (int i = 0; i < m; ++i) {
    s.A[i] = x % (n + 1);
    x /= (n + 1);
  }
  return s;
}

std::map<LL, int> _f;
int f(LL x, bool player) {
  if (_f.count(x)) return _f[x];
  State s = decode(x);

  bool isFinal = true;
  for (int i = 0; i < m; ++i)
    if (s.A[i] < n) isFinal = false;
  if (isFinal) return _f[x] = 0;

  int &ans = _f[x];
  ans = player ? -INF : INF;
  for (int i = 0; i < m; ++i)
    if (s.A[i] < n && (i == 0 || s.A[i] + 1 <= s.A[i - 1])) {
      ++s.A[i];
      int ans2 = f(encode(s), !player)
                + (player ? A[s.A[i] - 1][i] : -B[s.A[i] - 1][i]);
      ans = player ? std::max(ans, ans2) : std::min(ans, ans2);
      --s.A[i];
    }

  return ans;
}

int main() {
  n = readInt(); m = readInt();
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      A[i][j] = readInt();
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      B[i][j] = readInt();
  printf("%d\n", f(0LL, true));
  return 0;
}