更难游戏：题解

思路

最终保留下来的唯一获胜路径可以写成

$$1=p_1<p_2<\cdots<p_k=n.$$

路径上的平台不能被改成 $0$。为了不产生第二条获胜路径，两个相邻路径点 $p_s,p_{s+1}$ 之间，所有同样能够跳到 $p_{s+1}$ 的非路径平台都必须被改成 $0$。直接枚举整条路径仍然是指数级，因此需要记录“此前路径对右侧的影响范围”。

子任务 1：枚举修改集合

当 $n\le15$ 时，枚举前 $n-1$ 个平台是否改为 $0$。对每个集合按编号递推从平台 $1$ 到各平台的路径数，并把路径数截断为 $2$。若到平台 $n$ 的路径数恰为 $1$，用集合大小更新答案。

时间复杂度为 $O(2^n n^2)$，空间复杂度为 $O(n)$。

做法

状态设计

设 $dp[i][r]$ 表示：已经保证从 $1$ 到 $i$ 的获胜路径唯一，并且这条路径上 $i$ 之前最后一个保留平台的最远可达位置为 $r$ 时，最少改成 $0$ 的平台数。

考虑唯一路径上 $i$ 的前驱为 $j$。必须有 $j+a_j\ge i$，转移后的右端点为 $j+a_j$。此前状态的右端点不能越过 $i-1$，否则此前路径会直接绕过 $j$ 到达更右的平台。因此需要

$$\min_{j\le r<i} dp[j][r].$$

当我们按 $j=i-1,i-2,\ldots,1$ 递减枚举前驱时，维护区间 $(j,i)$ 内满足 $p+a_p\ge i$ 的平台个数 removed。这些平台若不在唯一路径上却能到达 $i$，就会形成额外到达方式，必须全部改成 $0$。于是转移为

$$dp[i][j+a_j]\gets\min\left(dp[i][j+a_j],\ \min_{j\le r<i}dp[j][r]+\textit{removed}\right).$$

初始状态为 $dp[1][1]=0$，答案为 $dp[n][n]$。

子任务 2：直接求区间最小值

对每次转移直接扫描 $dp[j][j\ldots i-1]$ 求最小值。共有 $O(n^2)$ 次转移，每次扫描 $O(n)$ 个状态。

时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$，可通过 $n\le200$。

满分算法：前缀最小值优化

预处理

$$pref[i][r]=\min_{i\le x\le r}dp[i][x].$$

转移中所需的区间最小值就是 $pref[j][i-1]$，可在 $O(1)$ 时间取得。每完成一行 $dp[i]$，从左到右构造对应的 pref 行即可。

总时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。由于所有测试用例的 $n$ 之和不超过 $3000$，逐个释放数组即可满足限制。

复杂度

枚举算法的时间复杂度为 $O(2^n n^2)$、空间复杂度为 $O(n)$；直接扫描区间最小值的动态规划时间复杂度为 $O(n^3)$、空间复杂度为 $O(n^2)$；满分算法时间复杂度为 $O(n^2)$、空间复杂度为 $O(n^2)$。

正确性说明

按唯一路径上的平台编号归纳。初始平台 $1$ 的路径唯一。假设状态已正确描述唯一到达前驱 $j$ 的最小代价：只允许此前影响区间在 $i$ 之前，排除了绕过 $j$ 的获胜路径；再把 $(j,i)$ 中所有能到达 $i$ 的非路径平台清零，便只剩从 $j$ 到 $i$ 的到达方式，因此新状态可行。反之，任意可行的唯一路径在相邻路径点 $j,i$ 之间都必须执行这些清零操作，并且此前影响区间不能越过 $i-1$，故转移不会漏掉更优方案。归纳到 $n$ 即得全局最优答案。