题解

思路

先建立按“已染红的 1 数量”划分的二次动态规划，再利用它的离散凹性，仅维护相邻状态的有序差分斜率。

做法

先假设所有位置都染成蓝色，基础收益为 $\sum b_i$，并令 $d_i=r_i-b_i$。把第 $i$ 位改成红色会增加 $d_i$，但每一对同时染红的 1...0 还要扣除 $1$。

子任务 1：枚举染色

当 $n\le18$ 时，枚举 $2^n$ 种红蓝方案。扫描字符串时维护此前染红的 1 数量；遇到染红的 0 时减去该数量。

子任务 2：按染红的 1 数量动态规划

设 $dp_k$ 表示处理完当前前缀、其中恰有 $k$ 个 1 被染红时的最大收益，初始 $dp_0=\sum b_i$。

• 遇到 1：选择蓝色时状态不变；选择红色时状态由 $k-1$ 转移到 $k$，并增加 $d_i$；
• 遇到 0：若此前有 $k$ 个红色 1，把该位染红的额外收益为 $d_i-k$，所以给 $dp_k$ 增加 $\max(0,d_i-k)$。

满分算法：维护 DP 的差分斜率

上述 $dp$ 关于 $k$ 是离散凹函数。记相邻差分为

这些差分按非增顺序排列。只需保留正差分，因为最终要求所有状态的最大值，而非正差分以后只会继续减小。

遇到 1 时，转移相当于向差分多重集合中插入 $d_i$；若 $d_i\le0$ 可直接丢弃。

遇到 0 且 $d_i>0$ 时，函数 $\max(0,d_i-k)$ 使 $dp_0$ 增加 $d_i$，并使最大的前 $d_i$ 个差分各减 $1$。实际差分数不超过 1 的数量，所以只处理前 $\min(d_i,m)$ 个。

用按差分值排序的随机 Treap 维护每个值的出现次数、子树总次数、子树值之和与整棵子树的懒加标记。按出现次数拆出最大的若干差分，对整棵子树打 $-1$ 标记，再合并边界相等值并删除降到零的差分。

最后答案为蓝色基础收益、所有 0 对 $dp_0$ 的增量以及正差分总和之和。

复杂度

暴力枚举为 $O(n2^n)$；中层动态规划为 $O(n^2)$、空间 $O(n)$；满分算法为 $O(n\log n)$、空间 $O(n)$。多组数据时把 $n$ 替换为所有测试用例长度之和。

正确性证明

二次 DP 逐位置穷尽当前位置的两种颜色，因此状态含义成立。其差分始终非增：1 的转移是与一个两点函数做最大加卷积，相当于有序插入一个新差分；0 的转移给前若干差分统一减一，仍保持凹性。Treap 完整模拟这两种差分变化，因此维护的函数始终与二次 DP 相同。最终取最大状态等于从 $dp_0$ 出发累加全部正差分，故算法输出最优收益。