题解

思路

把用于“解锁”的卡牌按原下标从小到大排列。设已经用于解锁的卡牌数值之和为 $s$，那么原牌堆的前 $\min(n,s+1)$ 张卡牌已经解锁。因而第 $i$ 张卡牌能够继续用于解锁，当且仅当 $s\ge i-1$。

若最终用于解锁的卡牌数值之和为 $s$，其余已经解锁的卡牌全部可以拿来得分，答案候选为

$$\operatorname{pre}_{\min(n,s+1)}-s,$$

其中 $\operatorname{pre}_k=\sum_{i=1}^{k}a_i$。

做法

子集枚举

当 $n\le20$ 时，枚举哪些卡牌用于解锁，按下标检查每次选择时是否已经可达，再计算上述候选值。复杂度为 $O(n2^n)$。

普通背包

令 $f_s$ 表示是否能让用于解锁的卡牌数值之和恰为 $s$。初始 $f_0=1$。扫描到第 $i$ 张卡牌时，只允许从 $s\ge i-1$ 的状态转移到 $s+a_i$。由于一次转移前 $s<n$，且 $a_i\le n$，只需保留到 $2n$ 的状态。复杂度为 $O(n^2)$。

位集优化

把所有 $f_s$ 压在一个位集中。删除下标小于 $i-1$ 的源状态后，整体左移 $a_i$ 位并取并集：

$$f\leftarrow f\;\mathbin{|}\;\bigl((f\gg(i-1))\ll(i-1+a_i)\bigr).$$

每次转移处理 $O(n/64)$ 个机器字，总复杂度为 $O(n^2/64)$，空间复杂度为 $O(n)$。

正确性说明

任何真实操作序列中的解锁卡牌都可以按原下标递增排列；在选择第 $i$ 张解锁卡牌前，恰有原牌堆前 $s+1$ 张卡牌可用，所以转移条件 $s\ge i-1$ 必要。反过来，满足该条件的每次 DP 转移都对应一次当前已经解锁卡牌的合法解锁操作，因此 DP 中的每个状态也都可实现。

状态 $s$ 可实现时，前 $\min(n,s+1)$ 张卡牌均已解锁。除已计入 $s$ 的解锁卡牌外，其余卡牌全部选择得分不会减少可达范围，所以候选值正是前缀和减去 $s$。枚举所有可达 $s$ 取最大值，即得到最优答案。

复杂度

满分算法的时间复杂度为 $O(n^2/64)$，空间复杂度为 $O(n)$。子集枚举的时间复杂度为 $O(n2^n)$；普通背包的时间复杂度为 $O(n^2)$。