P1099 [NOIP2007 提高组] 树网的核
如果有多条直径，对于任意一个直径的分差点，其在单调队列里的贡献就是另半条直径。而对于其其他分支，如果贡献大于那半条直径，那么这个贡献就会成为新的直径，与题设不符。因此，讨论任意一条直径即可。
P1136 迎接仪式
容易注意到，一个点可以与前面、后面交换，交换方式可以交叉，并不能做到静态查询子段贡献。一个可行的思路是，观察到有意义的交换实质是改变当前字母，而一一对应下来是改变的 j 和 z 数量相等。所以可以设 DP 数组 \(f_{i,j,k,0/1}\) 表示考虑到第 \(i\) 位，修改了 \(j\) 个 j 和 \(k\) 个 z，第 \(i\) 位取 \(0/1\) 的最大贡献，这样转移非常方便。由上面的分析，答案即为 \(\max\{f_{N,i,i,0/1}\vert0\le i\le\min(cnt_0,cnt_1,K)\}\)。
P1174 打砖块
最大的坑点在于打 Y 方块时需要子弹数不为 \(0\)。思索发现，这个限制在 Y 方块背包转移的时候是必要的，但是直接以 Y 方块结尾就会导致计算错误。那么，做一遍前缀背包和后缀背包，再枚举尾杀的那一列所有的情况即可。
P1285 队员分组
显然，直接处理选在一起的队员是极其困难的。正难则反，如果处理两个分开的队员，此时会发现 No solution 的判定转为了二分图判定。具体的，在两个不认识/单向认识的队员之间连一条边，如果出现奇环则一定分配不成功，因为队员只能分到两个队中。建新图后黑白染色判定。
剩下的部分考虑判定性 DP，黑点放一边，白点放一边，用上下转化的思想进行动态规划。绝对值不处理处理，加上一个大数直接开整。具体可以参考 P1282 多米诺骨牌 一题对于 P1282，看代码的时候发现不判断正负的代码可以过，在这里留个问号。
P1357 花园
好题。首先，需要复习以下矩阵乘法。矩阵乘法 \(C=AB\) 需要满足 \(c_A=r_B\)，结果 \(C\) 的 \(r\) 等于 \(r_A\)，\(c\) 等于 \(c_B\)。简洁来讲，\(n\times p\) 的矩阵 \(A\) 与 \(p\times m\) 的矩阵 \(B\) 相乘，得 \(n\times m\) 的矩阵 \(C\)。计算方面，对于 \(0\le i\le n,0\le j\le m\)，有 \(C_{i,j}=\sum\limits_{k=1}^pA_{i,k}\times B_{k,j}\)。易于理解一些，\(C\) 的第 \(i\) 行第 \(j\) 列的数为 \(A\) 第 \(i\) 行的数与 \(B\) 第 \(j\) 行的数依次相乘的和。
回到题目。不考虑环，单个花园与前后均有联系，但花园仅 C、P 两种，同时 \(2\le m\le5\)，第 \(i\) 位的转移会也只会与 \(i-m+1\) 到 \(i-1\) 的花园状态有关，所以可以用状态压缩表示当前转移的后 \(m\) 位。在每加入一个花园时，将状态 \(s\) 右移一位可以看作抛弃最后一个花园，再用 __builtin_popcount() 判断新状态合理性进行转移。这里用递推相对方便，方程为 \(f_{i-1,s}\to f_{i-1,\lfloor\frac{s}{2}\rfloor}\) 和 \(f_{i-1,s}\to f_{i-1,\lfloor\frac{s}{2}\rfloor+2^{m-1}}\)。没用编程语言，\(m-1\) 是因为压位储存。矩阵下标从 \(0\) 开始同理。
下一步，考虑环的情况。这里之讨论朴素 DP。在压掉第一维的情况下，算重的任务就要交给初始化了。钦定第 \(0\) 位的状态为 \(s\)，那么第 \(n\) 位只有状态为 \(s\) 的时候才是有效的合法状态。因为在 \(\bmod n\) 条件下，第 \(0\) 位和第 \(n\) 位是等价的，由于计数问题不会影响到后面，直接钦定得出的结果就是正确的。
接着，\(2\le n\le 10^{15}\)，直接递推的复杂度 \(O(n)\) 不可接受。类似 Fibonacci 数列的 \(F_i=F_{i-1}+F_{i-2}\)，这里的递推式也属于一维线性递推式，于是用矩阵乘法优化。两个点：一、单位矩阵 \(I\) 中，\(I_{i,i}=1\)，也就是说，单位举证在构造的时候正好相当于给每一种情况赋了初始值，因此不用再重新构造初始 \(1\times n\) 的矩阵，可以直接取 \(ans=\sum\limits_{i=0}^{2^m-1}res_{i,i}\)；二、转移矩阵是不固定的，所以还要考虑转移矩阵 \(t\) 的构造。假设由状态 \(s\) 可以转移到状态 \(s'\)，那么体现在结果矩阵上就是 \(f_{s',s'}\gets f_{s,s}\)。观察最开始给出的定义，因为一一对应，那么有 \(f_{s',s'}=\cdots+f_{s,s}\times t_{s,s'}+\cdots\) 中的 \(t_{s,s'}=1\)。反推过来，在构造 \(t\) 时如果状态 \(s\) 可以转移到状态 \(s'\)，就令 \(t_{s,s'}=1\) 即可。
P1370 Charlie的云笔记序列
\(n\) 的范围很容易看出来，需要从 \(O(n^2)\) 的单个区间统计转为 \(O(n)\) 的前缀/后缀区间统计。常见思路有设 \(f_n=\sum\limits_{i=1}^nF(i,n)\) 和设 \(f_n=\sum\limits_{1\le l\le r\le n}F(l,r)\) 两种，都可以将递推的时间复杂度降下一维。由这道题来看，如果后面状态统计时受前面某些状态影响，取第一种定义方式会显得方便一些。
如果没有重复数字，则 \(f_i=2f_{i-1}+2\)。分成两部分，\(2f_{i-1}=\sum\limits_{j=1}^{i-1}F(j,i-1)\times2\) 可以看作前面所有情况乘上最后一位选和不选两种情况，而这样统计出来的是 \(\sum\limits_{j=1}^{i-1}F(j,i)\)，所以还要加上 \(F(i,i)=2\)。重复的数字会产生重复的贡献，考虑去重，假设 \(a_{i'}=a_i\;(i'<i)\)，不难想到重复的方案是 \(a_{i'}\) 和前面拼接的方案以及单取 \(a_{i'}\) 的方案，也就是 \(f_{i'-1}+1\)。注意到每一个 \(a_{i'}\) 都是已经去过重的，更新 \(f_i\) 时取最近的 \(i'\) 相减即可。
一些其他的，在开头的第二种定义方式下，有 \(f_n=\sum\limits_{1\le l\le r\le n}F(l,r)=\sum\limits_{l=1}^n\sum\limits_{r=l}^nF(l,r)=\sum\limits_{r=1}^n\sum\limits_{l=1}^rF(l,r)\)，也就是常说的求和交换，一些情况下可以提供优化思路之类的。注意枚举范围。
P1389 一个关于序列的游戏
只能说非常毒瘤。首先需要明确，数列 \(\{A_1,A_2,A_3,A_4,A_5\}\) 可以按序取 \(\{A_2\},\{A_4\},\{A_1,A_3,A_5\}\)，所以直接向两头拓展的区间 DP 思路是完全错误的。接下来是基本思路。对于区间 DP，\(f_{i,j}\) 通常可以设为区间 \([i,j]\) 的最优解，或是满足某种条件的可以转移为最终状态的最优解。对于这题，显然取后面一种思路会更方便转移，因为区间可取可不取，在有限制的情况下无法判断连续性，前一种思路只能放弃。那么现在考虑设 \(f_{i,j}\) 为区间 \([i,j]\) 取满的最优解，容易想到 \(f_{i,j}=\max\limits_{k=i}^{j-1}\{f_{i,k}+f_{k+1,j}\}\)。然而并没有完。考虑到最开始列出来的取法，某一次取的元素可能非常不连续，无法用枚举断点的方式求解。但是注意到，题目所给的连续段的定义有一个很好的性质，即满足以最大元素为中心，左边以 \(1\) 递增，右边以 \(-1\) 递减。也就是说，转移的状态是可以确定的，因此考虑维护这样的子序列。可以设 \(g_{i,j,0/1}\) 为取 \((i,j)\) 中的数使 \([i,j]\) 最后成为连续增或减的连续段的最大总分。这里为了方便确定转移的连续性和数组 \(f\) 答案计算，转移过程中是保留 \(i,j\) 的，所以定义中使用了开区间。数组 \(g\) 相对来说好处理，因为留下的数需要保证连续，故有 \(g_{i,j,0}=\max\limits_{i\le k<j,A_k+1=A_j}\{g_{i,k}+f_{k+1,j-1}\}\)。在这个定义的基础上，求解区间最大总分的非连续转移可以表示为 \(f_{i,j}=\max\limits_{k=i}^j\{g_{i,k,0}+g_{k,j,1}+V_{A_k-A_i+A_k-A_j+1}\}\)，意义为将不在最终连续段的删去后将连续段删去。因为连续段值域一定连续且递增，所以整个区间长度等于左侧 \(A_k-A_i\) 加上右侧 \(A_k-A_j\) 补上 \(A_k\) 自己的 \(1\)。这样一来转移方程就构建完了。
对于最终答案，设 \(h_i\) 为取到 \(i\) 时的最佳答案，类似 LIS 的经典转移，\(h_i=\max(h_i-1,\max\limits_{j=0}^{i-1}\{h_j+f_{j+1,i}\})\)，意义为不取当前位和取前面最优解加一段最大总分。则 \(ans=\max\{h_i\}\)。
细节部分，首先注意到数组 \(f\) 和 \(g\) 在对方的转移式中均有出现，但是并没有关系，\(g\) 的转移只和长度小于当前状态的 \(f\) 有关，\(f\) 的转移值与长度小于等于当前状态的 \(g\) 有关，所以先转移 \(g\) 在转移 \(f\) 就能避免后效性。同时，\(g\) 转移时可能取到 \(f_{i+1,i}\)，在初始化的时候要设置为 \(0\)。除此之外，\(f\) 在实际转移中的 \(A_i,A_k,A_j\) 也许并不符合条件，尽管这种情况下 \(g\) 会使结果呈极小值，但 \(2A_k-A_i-A_j+1\) 很大概率会让数组 \(V\) 空间访问出错导致 RE，加个特判排除就没问题了。
其他两种做法待学习。
P1410 子序列
一个字，难。这道题是一个双序列类型的题目，算是不咋熟练。双序列问题通常为对称形式，可以以此压掉 DP 数组的维数。对于这个题，如果用判定性 DP 求解，将有 \(4\) 个维度，所以考虑降两维，先把 DP 数组用于记录另一个序列的结尾。由于越小的数越好接，数组存结尾最小值。还有一维，因为考虑到 \(i\) 时总长一定为 \(i\)，而且具有对称型，直接压掉。转移方面，有翻转所以顺推转移方便一些，若将 \(a_{i+1}\) 直接接入现在的数组，会有 \(f_{i+1,j+1}\gets f_{i,j}\;[a_i<a_{i+1}]\)；而放到那一边，会有 \(f_{i+1,i-j+1}\gets a_i\;[f_{i,j}<a_{i+1}]\)，也就是翻转序列。两者取 \(\min\)。式子比较难懂，要多消化。
P1412 经营与开发
每个星球的贡献/花费要受钻头耐久度影响，而且前面的星球选或不选会改变钻头耐久度。也就是说，正向考虑存在后效性，不能 DP。正难则反，我们从后往前考虑。一个钻头耐久的改变恰好会让后面所有贡献成比例改变，这个时候，我们可以钦定选择 \(i\) 号星球时耐久度为原来的 \(100\%\)，就相当于不受前面影响，来进行转移。因此，当为 \(i\) 为资源型星球有 \(f_i=\max(f_{i+1},x_i\times w+(1+0.01k)\times f_{i+1})\)；维修型也有类似转移。
P1437 [HNOI2004] 敲砖块
此题与 P1174 题名相似，内容也相似。注意到结果决策一定是由与输入方向相同的若干等腰直角三角形重叠而成，在枚举第 \(i\) 行第 \(j\) 列的转移时，上一列的遍历上限是 \(j+1\)。对于不取的情况假设存在第 \(0\) 排即可。最后统计答案也要在第 \(0\) 排取，保证三角形区域内所有点都要被取。
P1450 [HAOI2008] 硬币购物
首先不难发现，二进制拆分做法复杂度为 \(O(ns\sum\log d_i)\)，而数据范围为 \(n\le1000\)，\(d_i,s\le10^5\)，直接寄飞，需要从其他优化入手。观察到物品种类很少，为常数 \(4\)，且这是个多重背包计数问题，则有一种较为优秀的优化方式称作单调队列优化/前缀和优化。具体的，这类问题的 DP 转移式为 \(f_{i,j}\gets\sum\limits_{k=0}^{\min(d_i,\lfloor\frac{j}{c_i}\rfloor)}f_{i-1,j-k\times c_i}\)，或者写为 \(f_{i,j}\gets\sum f_{i-1,k}\;[min(0,j-d_i\times c_i)\le k\le j,k\equiv j\pmod{c_i}]\) 的形式。重点在于后一个式子中 \(k\) 的限制，因为 \(f_{i,j}\) 的转移只和 \(\forall k\equiv j\pmod{c_i}\) 有关，我们可以将所有 \(f_{i-1,j}\) 按 \(j\bmod c_i\) 分组维护一段区间内的和，以此转移。这样一来，复杂度就与物品个数 \(d\) 无关了，优化为 \(O(n4s)\)，其中 \(4\) 代表物品个数。
但是，还是过不了，只能再想方向优化。思考一个弱化版的问题，如果只有一个硬币受个数限制，方案数是多少呢？显然，对于其他三种硬币可以用完全背包求解，对于这一个硬币用多重背包求解，这是可行的；然而，用所有硬币的完全背包结果排除这种硬币超限制的情况，在物品消耗限定和多次询问的条件下减少了做完全背包的次数，是一种更优的解法。使用钦定法计算不合法情况，假设目标钱数是 \(m\)，用 \(c\) 表示硬币个数，\(w\) 表示硬币价值，有不合法方案数为 \(f_{m-(c+1)\times w}\)，即钦定已选 \(c+1\) 个限制硬币，剩下硬币随便选。这样一来，取法一定超过限制。接下来考虑如何拓展。此时题目的解法已经有了容斥的雏形，我们往容斥上面靠，发现多种硬币超限制的情况正好符合容斥定理的形式。所以一开始 \(O(4\max s)\) 预处理所有完全背包结果，再用 \(O(2^4)\) 位运算枚举硬币子集进行容斥，即可过掉这道题。
P1453 城市环路
两种做法。
第一种，容易看出给定的图是一个基环树，因此考虑分开处理环和分支。分支部分是经典最大权独立集问题，树形 DP 可以解决。判环并单独预处理后思考环上的 DP。普通环形 DP 的一般思路是倍长原数组，用前缀答案相减。但这道题中，每一个点有选或不选两种状态，而且两种状态的转移互不影响，并不能像正常情况倍长来做。观察普通环形 DP 与这里 DP 的差别：倍长做法，是因为起点不同时，所得区间答案不同；而此处的 DP 整个环互相影响，不论从哪个点出发最优答案总是相同，所以我们钦定一个点作为区间起点，枚举这个点的情况做线性 DP，分类统计答案即可。
第二种，思考加入的第 \(n\) 条边的本质，由于一条边的限制作用是让两端至少一端不取，这条多出来的边 \((u,v)\) 实质上就是强制 \(u\) 不选或 \(v\) 不选。不考虑多加一条边的情况下以两点为根分别跑一次树形 DP，取答案为 \(\max(f_{u,0},f_{v,0})\)。细节方面，由于不需要获取环上节点信息，可以用并查集维护连通性判断成环边。
P7961 [NOIP2021] 数列
如果这是 NOIP，那我就死了。重中之重，注意数组大小。题目中的 \(S\) 以拆位形式给出，故考虑逐位 DP。由于 \(a_i\) 可以相同，所以转移过程中会出现进位的情况，需要从低位向高位考虑，同时单独统计一维表示进位。综合上述，考虑设 \(f_{a,b,c,d}\) 为转移到 \(S\) 的第 \(a\) 位时（即在考虑 \(v_a\) 的贡献的时候），安置了 \(b\) 个数，存在 \(c\) 个 \(1\)，且向这一位进位 \(d\) 个一的权值和。显然，刷表法在此处更为方便。我们枚举当前位加入的 \(1\) 的个数 \(x\)，那么，下一步的状态应为 \((a+1,b+x,c+(x+d)\%2,\lfloor\dfrac{d+x}2\rfloor)\)。意义是，到了下一位时，这一位占了 \(x\) 个序列位置，当且仅当 \((x+d)\) 个 \(1\) 进位后有剩余时多出一个 \(1\)，取一半进位。接下来考虑转移带来的贡献，对于每一次加入 \(x\) 个 \(2^a\)，贡献为 \(f_{a,b,c,d}\times v_a^x\)；同时，将 \(x\) 个数安排在剩下的 \(n-a\) 个位之中，方案数为 \(C_x^{n-a}\)。因此，\(f_{a+1,b+x,c+(x+d)\%2,\lfloor\frac{d+x}2\rfloor}\gets f_{a,b,c,d}\times v_a^x\times \dbinom{n-a}x)\%mod\)。对于初始状态，有不选任何数的时候权值和为 \(1\)，所以令 \(f_{0,0,0,0}=1\)；对于终止状态，就是考虑完第 \(m\) 位到第 \(m+1\) 位，且 \(n\) 个数填满的时候，枚举此时已有 \(1\) 的个数为 \(i\) 和进位数 \(j\)，有 \(i+\text{popcount}(j)\le k\) 时才为合法，统计下来即可。
P1472 [USACO2.3] 奶牛家谱 Cow Pedigrees
一题多解好评。
做法一：考虑正推构造，用 \(f_{i,j}\) 表示考虑到第 \(i\) 层放置了 \(j\) 个点的方案数。显然，在第 \(i\) 层的叶子数会影响统计，增添一维用 \(f_{i,j,k}\) 表示考虑到第 \(i\) 层，前一层放了 \(j\) 个，总共放 \(k\) 个的方案数。（原题中的 \(k\) 用 \(m\) 代替。）枚举当前位放的叶子数 \(l\)，有 \(0\le l\le2\times j\) 以及 \(2\mid l\)。上一层每个叶子有不放或放两个两种选择，这层安置方案数即为 \(\dbinom j{\frac l2}\)。整理得转移式 \(f_{i,j,k}\times\dbinom j{\frac l2}\to f_{i+1,l,k+l}\)。注意初始化 DP 数组以及组合数，取答案 \(ans=\sum f_{m,i,n}\)。
做法二：考虑正推统计，同样用 \(f_{i,j}\) 表示考虑到第 \(i\) 层放置了 \(j\) 个点的方案数。每次转移相当于给一个节点加一个左子树和右子树，但注意到层数与点数这俩玩意儿没什么很强的关联性，直接转移复杂度爆炸。从方案数求和入手，用前缀和与容斥思想，记 \(pre_{i,j}=\sum\limits_{k=1}^if_{k,j}\)，即深度不超过 \(i\) 的方案总数。故有 \(f_{i,j}=\sum\limits_{1\le k<j,2\nmid k}pre_{i-1,k}\times pre_{i-1,j-k-1}\)，其中 \(2\nmid k\) 是因为完满二叉树节点数一定为奇数，\(j-k-1\) 是因为排除当前根节点。可以直接省掉 \(f\) 数组求 \(pre\)，最终答案 \(ans=pre_{m,n}-pre_{m-1,n}\)。
做法三：kkksc03 的前缀和。
P1493 分梨子
被 DP 骗了。对于这种含有两个元素的不等式，算上不等式上下界带来的二维偏序，一种解决方案是 CDQ 分治。但毕竟是蓝题，有更加简便的做法。由于给出的不等式包含最小值，故考虑枚举最小值，逐个判定是否合理。但这样一来，复杂度是 \(O(n^3)\) 的，需要优化。从式子入手，\(C_1\times(A_i-A_0)+C_2\times(B_i-B_0)\le C_3\)，化简移项使有关 \(i\) 的和有关最小值的分开来，得到 \(C_1\times A_i+C_2\times B_i-C_3\le C_1\times A_0+C_2\times B_0\)。这样一来，左边的式子就是关于 \(i\) 的一个固定值。那么借鉴单调队列思想，我们把梨子按左半部分升序排列，考虑让右边具有单调性。此时一种可行的思路是随机枚举 \(A_0\)，然后升序枚举 \(B_0\)，这样就能保证梨子枚举范围单调。因为当 \(A_0\) 确定的时候，右半部分变为关于 \(B_0\) 的一次函数，\(B_0\) 单调，一定不减。统计答案部分，虽然梨子范围单调，但是不能保证之前的 \(B_i\) 都大于当前枚举 \(B_0\)，需要排除贡献。显然，树状数组是可以解决的，但又是由于 \(B_0\) 保证不减，一次拓展最多只会多算上一次的 \(B_0\)，所以开个桶计数即可。为防止重复减少，注意清零。内层单调队列均摊 \(O(1)\)，总时间复杂度降至 \(O(n^2)\)，树状数组 \(O(n^2\log n)\) 也能过。
P1514 [NOIP2010 提高组] 引水入城
第一个结论，一个有解的情况下，一个蓄水场覆盖的沙漠城市一定连续。否则假设某蓄水场只取到 \([l,x]\) 和 \([y,r]\) 两个区间，则这个蓄水场的流域是个扇环，类似于 h 形，区间 \((x,y)\) 就被包括在中间的盆地里。这样一来其他蓄水场都进不去，必定无解。有了这点，无解直接判，有解做线段覆盖。接下来考虑求蓄水场覆盖区间。朴素的 DFS/BFS 复杂度高达 \(O(nm^2)\)，可以考虑 DP \(O(nm)\) 求解，但是水流是四联通，可以往上走，不能直接 DP，因此需要用记忆化搜索。设 \(l_{x,y}\) 表示到了第 \(x\) 行第 \(y\) 列可以覆盖到的最左点（右端同理），则有 \(l_{x,y}\gets\min\{l_{fx,fy}\}\)，其中 \((x,y)\) 可以直接到达 \((fx,fy)\)。直接记搜就完了。
P1539 [TJOI2011] 01矩阵
由于 \(n\times m\le225\)，一定会有 \(\min(n,m)\le\sqrt{225}=15\)，所以当 \(n<m\) 时按梯形（三角）翻转原图进行状压 DP 即可。算是根号的小 trick。
P1545 [USACO04DEC] Dividing the Path G
首先，端点不算重合，而这很不好处理，所以令点 \(i\) 表示第 \(i\) 个草块，同时有 \(S_i\gets S_i+1\)（下同）。其次，喷灌器放端点两边都能喷到，不如看成长度为 \(len\;(2\mid len\land len\in[2\times A,2\times B])\) 的覆盖线段。考虑题目，喷灌器不相交，全覆盖，就是个分段问题。继续思考，发现一个性质，两个草区相交时一定被同一个喷灌器灌溉，这很好证明。那么对于合并后的区间 \([l,r]\)，一旦 \([l,r)\) 存在了一个喷灌器右端点，那么就不合法了。那么就有朴素动态规划式：
\[f_{i}=\begin{cases}0&i=0\\\inf&i\in[l,r)\lor2\nmid i\\\min\limits_{i-2\times B\le j\le i-2\times A}{f_j}+1&\text{otherwise.}\end{cases} \]现在处理细节。合并完的草区不能取，所以要标记。这个东西本质时区间修改，虽然暴力过了 \(10^6\)，但明显可以用线段树优化。实际上差分是个更有效率的解决方法，毕竟在 DP 线性扫描的过程中可以顺便前缀和，判断当前草块被多少草区覆盖。对于草区的合并，看似复杂，实际上根本不用管，分开处理就行了。不论是线段树还是差分，只要判断某一草块上有没有覆盖过就行了，覆盖多少次不用管；而从草区方面来看，举个例子，单独标记 \([a,b)\) 和 \([b,c)\)，效果是 \(b\) 会被标记但 \(c\) 不会，符合合并后的效果，其他情况差不多，因此可行。对于下面带区间的最小值，用单调队列会比线段树快很多，只不过依旧一眼线段树优化，复杂度高了点。
P1578 奶牛浴场
最大子矩形问题。注意与最大子矩阵问题不同，无法用单调栈解决。预计单开专题。
P7914 [CSP-S 2021] 括号序列
主要是两个点。一、对于这种区间计数问题，通常线性 DP 和区间 DP 都是可以做的，但这道题里面的“超级括号序列”并不是对称的（一边有 * 一边没 *），这种对转移方向有限制的就只能用区间 DP 了；二、状态设计一定是朝着方便转移去靠的。如果直接想一开始一样定死了左右为括号，转移和去重会非常麻烦。那么把所有的转移涉及到的部分拆开去设计状态，也就是同时记录 AS 和 SA 的情况就好了。同时为了防止用 * 拼接时的长度限制问题，可以考虑对全 * 单独记一个状态。