Codeforces Round 1082 (Div. 2) E

今天看题解给我看红温了，第一次遇到dp转移方程给了公式但是没有给全甚至没有说明没有给全的情况，分析了三小时硬是分析不出来。

设所选子序列在原字符串中的起始下标为 s1​，结尾下标为 sk​。

定义'('对前缀和的贡献为 +1，')'为 −1，并记presum[i]为原字符串前 i个字符的前缀和。

1. 按结尾字符分类讨论

（1）结尾是'('的情况​

右移后，这个'('会移动到子序列的开头 s1​位置。此时从 s1​开始的前缀和只会增加或不变，不可能减少，因此绝对不会导致新序列非法。

以'('结尾时，其前面的子序列（包括空序列）可以任意选择。

（2）结尾是')'的情况​

右移后，这个')'会移动到 s1​位置，此时从 s1​开始的前缀和只会减少或不变。

• 若不变，显然不会导致非法；

• 若减少，则必须小心，因为可能使前缀和低于 0，破坏括号序列合法性。

2. 前缀和的变化规律

以样例3说明：

原串："(()())"，选第 3 到第 5 个位置（下标从 1 起），即"())"，右移后得到"(())()"。

• presum[3]不变（因为 s1​之前的字符未动）；

• presum[4]原本是 2，右移后变为 0。

一般规律：

若所选子序列中某个位置原来是'('，右移后它可能被更靠后的字符替换，导致从该位置起直到某个位置之前，前缀和减少 2；

若原来是')'，则替换后前缀和不变。

因此，关键在于所选子序列中'('的位置。

3. 合法性条件的提炼

考虑以位置 i结尾、且以')'结尾的子序列，其右移后仍合法的条件：

• 若 S[i]=’)’，则不论前面怎么选，右移后这个')'移到开头，不会使前缀和低于 0（因为原串合法，开头一定是'('才会出现')'）。

• 若 S[i]=’(’，则右移后它可能被后面的')'替换，导致从开头到该位置的前缀和减少 2。因此，必须保证从子序列开头到最后一个’(’之后一个位置，其前缀和都≥ 2，这样减少 2 后才不会低于 0。

4. 尝试用 DP 计数

定义dp[i]表示以位置 i 结尾，且右移后仍合法的非空子序列个数。

转移考虑最后一位是'('或')'的情况：

• 最后一位是')'：前面可以接任意以')'结尾的合法子序列，即前面所有dp[j]（其中 S[j]=’)’）都可以直接转移过来，并且还可以单独以这个')'作为一个子序列（+1）。

• 最后一位是'('：前面只能接那些从子序列开头到当前位置之前所有前缀和 ≥ 2​ 的合法子序列。这对应着一个“安全”的前缀和区间，需要用一个计数器维护。

因此，可以维护两个累加值：

• cnt1：前面所有以')'结尾的dp值之和（对应上述第一种情况）。

• cnt2：前面所有“安全”的以'('结尾的dp值之和（对应上述第二种情况）。

转移时：

dp[i]=1+cnt1+cnt2

并按照 S[i]更新cnt1和cnt2：

• 若 S[i]=’)’，将dp[i]加入cnt1；

• 若 S[i]=’(’，将dp[i]加入cnt2；

• 若当前位置前缀和降为 0，说明进入了一个新的“最低点”，之前累积的cnt2不再安全，需要清零。