核心思路

本题要求对于每个给定的比赛结果序列，找出所有赌注中能获得的最大净收益及达成该收益的赌注数量。关键在于利用状态压缩和动态规划高效处理所有 $2^n$ 种可能的结果序列。

关键观察

1. 序列编码：每个预测序列 $p_i$ 和结果序列 $w_i$ 都可以用一个 $n$ 位二进制数表示，其中第 $j$ 位表示第 $j$ 场比赛的预测/结果
2. 收益计算：对于给定的结果序列 $w$ 和预测序列 $p$，收益为：$$\text{收益} = \sum_{j=1}^n \begin{cases} a_j & \text{if } w_j = 0 \text{ and } p_j = 0 \\ b_j & \text{if } w_j = 1 \text{ and } p_j = 1 \\ 0 & \text{otherwise} \end{cases}$$

核心算法：按位DP

状态定义

设 $dp[S]$ 表示对于某个中间状态 $S$（$n$ 位二进制数）的最大净收益和对应的赌注数量。

算法流程

1. 初始化：将每个赌注的预测序列 $p$ 编码为整数 $x$，初始化 $dp[x] = (-k, 1)$，其中 $k$ 是赌注价格

2. 逐位处理：对于第 $i$ 场比赛（$i = 0$ 到 $n-1$）：

   • 遍历所有状态 $S$
   • 如果 $S$ 的第 $i$ 位为 $0$（预测第一队胜）：
     • 保持预测不变：收益增加 $a_i$
     • 翻转预测：收益不变（因为预测错误）
   • 如果 $S$ 的第 $i$ 位为 $1$（预测第二队胜）：
     • 保持预测不变：收益增加 $b_i$
     • 翻转预测：收益不变

3. 状态转移：使用 add 函数合并状态，当收益相等时累加计数，否则取较大值

最终结果

处理完所有 $n$ 场比赛后，$dp[w]$ 即为结果序列 $w$ 对应的答案：

• $dp[w].first$：最大净收益
• $dp[w].second$：达成该收益的赌注数量

算法优势

• 高效性：时间复杂度 $O(n \cdot 2^n)$，在 $n \leq 20$ 时可行
• 完备性：同时计算所有 $2^n$ 种可能结果序列的答案
• 正确性：通过逐位处理确保考虑所有可能的预测组合