# 优选猫咪：按选择数量动态规划

出题人解法：子集枚举与加权动态规划。Codex（GPT-6）：将动态规划滚动为一维数组，明确不可达状态、64 位数值界及剪枝验证。

## 首选动态规划

最终选择数 $k$ 固定，第 $j$ 个选中的评分要乘以 $3^{k-j}$ . 令 $f_{i,j}$ 表示从前 $i$ 只猫中恰好选 $j$ 只时，按它们在最终答案中的权重得到的最大贡献。

初始 $f_{0,0}=0$ ，其他状态不可达。对第 $i$ 只猫，分不选与选两种情况：

$$f_{i,j}=\max\left(f_{i-1,j},\ f_{i-1,j-1}+v_i3^{k-j}\right)$$

只从可达状态转移；$f_{i,0}=0$ . 预先计算三的幂，答案为 $f_{n,k}$ .

一维数组按 $j=\min(i,k),\ldots,1$ 递减更新。此时 $f_{j-1}$ 仍是上一行的值，不会在同一轮重复选取第 $i$ 只猫。$k=0$ 时没有转移，答案保持零。

## 正确性

从前 $i$ 只猫中选 $j$ 只的任一方案，要么不含第 $i$ 只，要么包含它。前者归入 $f_{i-1,j}$ ；后者因为编号最大，它正好是第 $j$ 个选择，贡献为 $v_i3^{k-j}$ ，其余部分由 $f_{i-1,j-1}$ 给出。两类覆盖且互斥，取最大值获得正确最优解。归纳得到全部状态及最终答案正确。

评分为负时仍需恰好选择 $k$ 只，不能把不可达状态初始化为零。程序使用远小于合法答案的哨兵，并在相加前判断可达性。

## 数值与复杂度

任何合法方案满足

$$|\mathrm{score}|\le1000\sum_{j=0}^{k-1}3^j=1000\frac{3^k-1}{2}$$

当 $k\le25$ 时，右端不超过 $423644304721000$ ，必须使用 64 位整数；C++ 的 `long` 不保证在所有平台上都是 64 位，程序采用 `long long` .

时间为 $O(n(k+1)+1)$ ，空间为 $O(k+1)$ ，包括预计算幂与滚动数组。写成 $k+1$ 也覆盖零选择时读取输入的成本。

程序见 [std.cpp](std.cpp)。出题人的[子集搜索](solution-alternative.zh.md)及 [alternative.cpp](alternative.cpp)保留为备用方案，最坏时间 $O(2^n)$ 、空间 $O(n+1)$ ，在当前 $n\le25$ 的正式数据上通过。动态规划合并相同的前缀与选择数状态，渐进时间更好，故作为首选。全负数、零选择、全部选择、中间选择数与极端评分见 [plan.json](tests/plan.json)，性能见[评测说明](../../../docs/评测环境与性能.md)。