优选猫咪：按选择数量动态规划¶
出题人解法：子集枚举与加权动态规划。Codex（GPT-6）：将动态规划滚动为一维数组，明确不可达状态、64 位数值界及剪枝验证。
首选动态规划¶
最终选择数 \(k\) 固定，第 \(j\) 个选中的评分要乘以 \(3^{k-j}\) . 令 \(f_{i,j}\) 表示从前 \(i\) 只猫中恰好选 \(j\) 只时，按它们在最终答案中的权重得到的最大贡献。
初始 \(f_{0,0}=0\) ，其他状态不可达。对第 \(i\) 只猫，分不选与选两种情况：
只从可达状态转移；\(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\) 只，不能把不可达状态初始化为零。程序使用远小于合法答案的哨兵，并在相加前判断可达性。
数值与复杂度¶
任何合法方案满足
当 \(k\le25\) 时，右端不超过 \(423644304721000\) ，必须使用 64 位整数；C++ 的 long 不保证在所有平台上都是 64 位，程序采用 long long .
时间为 \(O(n(k+1)+1)\) ，空间为 \(O(k+1)\) ，包括预计算幂与滚动数组。写成 \(k+1\) 也覆盖零选择时读取输入的成本。
程序见 std.cpp。出题人的子集搜索及 alternative.cpp保留为备用方案，最坏时间 \(O(2^n)\) 、空间 \(O(n+1)\) ，在当前 \(n\le25\) 的正式数据上通过。动态规划合并相同的前缀与选择数状态，渐进时间更好，故作为首选。全负数、零选择、全部选择、中间选择数与极端评分见 plan.json，性能见评测说明。