CF1987D World is Mine 题解

---

题意

A 和 B 比赛吃蛋糕，蛋糕共有 $n$ 个，每一个蛋糕有一个美味值 $a_i$。

A 与 B 交替着吃，A 先吃，且 A 需要保证 A 本次吃的蛋糕美味值要严格大于先前 A 所吃的所有蛋糕；接着，B 可以吃掉任意一个蛋糕（当然，已经被吃掉的肯定不行），直到有一方无蛋糕可吃为止，游戏结束。

设 $x$ 为游戏结束时，A 吃下的蛋糕总数。已知 A 和 B 都足够聪明，A 想要最大化 $x$ 而 B 想要最小化 $x$，求双方都按自己的最优策略吃蛋糕时，$x$ 将会是多少。

$n \le 5000$

---

思路分析

如果所有蛋糕美味值两两不同

显然 B 做什么复杂的决策是没有意义的，只要 A 不傻就会从最小的蛋糕开始往上递增着吃，B 最多只能吃掉一半的蛋糕。这里就和博弈没什么关系了。所以题目的重点就在于处理那些美味值相同的蛋糕。

处理相同美味值

对于一批美味值相同的蛋糕，A 想要"拿下"这批蛋糕只需要吃掉其中的一个就可以了，因为吃蛋糕的顺序是严格的单调递增，多出来的那些蛋糕没有意义；而 B 要考虑的就多了——需要在 A 吃掉其中任意一个之前把它们全部吃掉。

也就是说，假设这批相同美味值的蛋糕有 $p$ 个，A 让这批蛋糕对 $x$ 产生一个贡献只需要消耗 $1$ 回合就行，而 B 要拦截下这个贡献需要 $p$ 回合。

最优决策框架

再结合 A 从小往大吃一定不劣 的性质，我们可以对 $a$ 排序、将 $a$ 相同的蛋糕合并后依次从小往大考虑。对每批美味值相同的蛋糕 $i$：

• 不拦截：B 选择把这个 $i$ 让给 A 吃，来为自己争取到一个空闲回合，用来拦截后面的蛋糕。
• 拦截：B 选择用已经积累好的空闲回合直接出手拦截这个 $i$，代价就是这批 $i$ 蛋糕的总个数 $c_i$。

---

DP 设计与转移

设计状态 $f_{i,j}$ 表示当前考虑到了第 $i$ 批蛋糕，当前 B 已经攒下了 $j$ 个空闲回合时，已经产生的最小贡献（即 A 到目前为止吃到的最少蛋糕数，因为 B 希望最小化 $x$）。

转移方程：

$$f_{i,j} = \min\big( \underbrace{f_{i+1,\;j+1} + 1}_{\text{不拦截：A 吃，B 攒一个空闲回合}},\;\; \underbrace{f_{i+1,\;j-c_i}}_{\text{拦截：B 消耗 }c_i\text{ 个空闲回合}} \big) $$

后者需要保证 $c_i \le j$。

边界：当 $x > tot$（所有批次处理完毕）时，$f = 0$。

最终答案即为 $f_{1,0}$。

---

复杂度

• 状态数 $O(n^2)$，转移 $O(1)$。
• 时间复杂度和空间复杂度均为 $O(n^2)$。

由于 $\sum n \le 5000$，完全可以通过。

---

AC 代码

const ll maxn = 5005;
ll f[maxn][maxn];
ll a[maxn], tot, b[maxn];
ll n;

ll dfs(ll x, ll t) {  // 记忆化搜索
    if (x > tot) return 0;
    if (~f[x][t]) return f[x][t];
    ll res = dfs(x + 1, t + 1) + 1;           // 不拦截
    if (t >= b[x]) res = min(res, dfs(x + 1, t - b[x]));  // 拦截
    return f[x][t] = res;
}

void solve() {
    n = R;
    tot = 0;
    for (ll i = 1; i <= n; i++) {
        a[i] = R;
        for (ll j = 0; j <= n; j++) f[i][j] = -1;  // 多测清空
    }
    sort(a + 1, a + 1 + n);
    for (ll i = 1; i <= n; i++) {
        if (a[i] > a[i - 1])
            b[++tot] = 1;
        else
            b[tot]++;
    }  // 合并相同美味值
    we(dfs(1, 0));
    return;
}