Readme

3628.Maximum-Number-of-Subsequences-After-One-Inserting

这道题的迷惑性在于很容易误导用DP来解。我们容易设计成dp[i][j][k]表示前i个元素里、用了j次insertion（0,1），能出现多少个以字符k结尾（L,C,T）的合法subsequence。但是这个dp值实际上允许我们在任意位置插入，并且统计了所有的subsequence的总和。这与题意要求是不一样。题目里要求的是确定一个insertion位置的情况下，能出现多少个合法的subsequence。在所有插入的位置中，再选一个最大的结果。

本题的正解是利用subsequence的长度仅有3，以中心字符为C为入手点，考察左边L和右边T的分布与组合。具体分情况讨论如下：

1. 不考虑任何插入操作。我们预处理得到leftL[i]表示i左边有多少个L，rightT[i]表示i右边有多少个T。于是对于每个字符如果s[i]='C'，那么leftL[i]*rightT[i]就是以i为中心的subsequence的个数。然后全局累加，结果记为count。

2. 考虑插入L，我们需要计算以这个新插入的L开头的合法子序列的个数。假设我们将L插在i的左边，那么等价于计算i右边（包括i）存在多少个CT。我们可以从右往左遍历，对于每个C，统计它右边有多少个T，这样就可以加入CT的统计。

3. 同理考虑插入T，我们需要计算以这个新插入的T结尾的合法子序列的个数。假设我们将T插在i的右边，那么等价于计算i左边（包括i）存在多少个LC。我们可以从左往右遍历，对于每个C，统计它左边有多少个L，这样就可以加入LC的统计。

4. 最后考虑插入C。这个比较简单，假设我们将C插在i的左边，那么leftL[i]*rightT[i-1]就是以该C为中心的subsequence的个数。

注意，最终我们需要取2,3,4三种答案的最大值，与第一种情况的count相加。