优选猫咪：带可行性剪枝的子集搜索¶
出题人的子集搜索与配套讲解中的剪枝。Codex（GPT-6）：预计算权重、统一 64 位类型及边界验证。程序为 alternative.cpp，是动态规划的备用方案，能通过当前完整数据。
搜索状态¶
状态为当前处理位置 \(p\) 、已经选择的数量 \(j\) 、已有贡献 \(s\) ，位置从零开始。若 \(j=k\) ，更新最大答案并返回；若剩余 \(n-p\) 只猫少于 \(k-j\) ，直接返回。否则分支为：
- 选择当前位置，进入 \((p+1,j+1,s+v_p3^{k-j-1})\) .
- 不选择当前位置，进入 \((p+1,j,s)\) .
三的幂提前计算。答案初始为足够小的负数，不能初始为零；当 \(k=0\) 时第一个出口立即得到零。
正确性与复杂度¶
每个合法下标集合对应唯一的一条选或不选路径。位置单调增加，所以所选顺序满足题意。新选中的位置是第 \(j+1\) 个，因此它的权重为 \(3^{k-j-1}\) . 选满以后剩余位置必然不选，可以直接更新答案；剩余数量不足时不存在合法补全，可以剪枝。这两种提前返回不会丢失任何合法最优方案。
二叉决策树至多有 \(O(2^n)\) 个节点，每个节点在权重预处理后只做常数工作。总时间为 \(O(2^n)\) ，输入、幂数组及递归栈合计 \(O(n+1)\) 空间。负数与重复值不改变枚举逻辑。对于更大的 \(n\) ，应采用多项式时间的动态规划；本程序的通过结论仅针对当前范围和测量数据。