题解：CF2029G Balanced Problem

Ewig_Milan · 2026-11-09 22:01:59 · 题解

主播主播，需要绕弯子的状态设计还是太吃操作了，有没有能无脑设计状态的做法？

有的兄弟，有的。

考虑转化题意：

前缀 + 后缀操作？任意次数操作？太复杂了！
直接前后缀操作两两配对，转化为全局 +1 然后区间 +1 或 -1 操作（配不上的和空操作配对就行）。

发现全局 +1 是假的：v-1\to v 就行了。紧接着发现 v=0 时继续操作是显然不优的。关于证明，可以回到原操作手玩一下“前后缀均操作大于 v 次”的情况。

于是题意转化为了：对原始序列进行至多 v 次区间 +1 或 -1 操作，最大化 0 位置的权值和。

进一步注意到 +1 操作是冗余的（这个稍微手玩一下就行）。

然后你就发现，在还未开始做的情况下，这道题被你转化成了一道 DP 绿题：f(i,j) 表示前 i 个数做了 j 次操作的最大权值和。

关于那个 n\to V 的转化，其实和“紧接着发现 v=0 时继续操作是显然不优的。”这一步的证明差不多，手玩可证，严谨可看别的题解。