「BJOI2014」路径
由于数据范围很小，图对于我们来说就没有什么问题了。
将步数、括号到了第几层，上一个字符是什么记入状态。转移要注意很多细节，判掉不合法的。
这里注意，由于 0 是否作为第一个是我们所关心的，那么在设计 \(mp\) 的时候，要多记一个种类 \(~0\)，表示不是前导 \(0\) 的 \(0\)。
「雅礼集训 2019 Day7」Inverse
前缀和优化dp
传统的整体记录的状态无法解决问题。
看到数据范围很小，那么令 \(dp(i,j,k)\) 表示在 \(k\) 轮之后 \((i,j)\) 是逆序对的概率。
优化 \(O(n^4k)\) 的 DP。对于每个 \(i,j\) 我们枚举 \(l,r\) 进行统计。推式子有用前缀和优化。
CSP-S 2024 染色
还是好好想想整个思路。
设计过的状态：\(f_{i,0/1}\) 表示当前前是什么颜色， \(f_{i,j}\) 表示当前到第 \(i\) 个数，连续相同的颜色段长度为 \(j\)。前者因为无法记录进去先前的转移位置而错误；后者因为转移是 \(O(n^4)\) 的且没前途，加上时间不够，最后就没打。回来后又想到 \(f_{i,j}\) 并且记录后一个位置的价值。
从第二个状态的疑点出发：这个状态是一块一块转移的，并不能做到相邻位置的转移。如果可以做到这点，那么复杂度就会下来。那么我们把 \(f_{i,j}\) 定义为前 \(i\) 个数，前一个与之颜色不同的是 \(j\)。\(f_{i,j} + val(i,j) \to f_{i+1,i},f_{i,j} + val(i,i+1) \to f_{i+1,j}\)。
但是这又如何优化呢？我们之前有一个困惑：无法很好记录价值，这是因为惯性思维地选择了一段的右端点作为转移的关键点。但是如果我们以 \(i\) 与 \(i-1\) 颜色不同作为状态呢？设 \(g_i\) 表示 \(i\) 与 \(i-1\) 颜色不同，前 \(i\) 个的价值。这样我们在后面找前面的价值时就可以直接把 \(i-1\) 拿过去。现在有转移：\(g_i \gets \max g_j + val(j-1,i) + pre_{i-1}-pre_{j}\) 把 \(j\) 都移到一起：\(g_i \gets \max g_j - pre_j + val(j-1,i) + pre_{i-1}\)。那么分别记录某一颜色的 \(\max g_j - pre_j + a_{j-1}\) 和前缀 \(\max g_j - pre_j\)。
Costly Binary Search
DP 状态优化。发现答案比 \(n\) 还小，进行 下标和值互换 的状态优化。
NOIP2021 方差
两层：1. 看出来了操作的本质是交换差分；2. 发现贪心：所有的差分是一个单谷。
第一个看出来就可以全排列了，有 20pts。（我 next_permutaion 前没排序爆挂一个点 qwq）
我没看出来第 2 个，其实观察样例是可以得出来的。那剩下的只有 DP 了。
\(f_{i,j}\) 表示放到了第 \(i\) 个差分，\(\sum a_i\) 为 \(j\) 的最小 \(\sum a_i^2\)。其实可以不用管 \(a_1\)，因为算的是方差。
接下来就分两种转移：
放右边：\(f_{i,j+\sum d} \gets f_{i-1,j} + (\sum d)^2\)
\(\sum (a_i + d)^2 = \sum a_i^2 + 2a_id+d^2=\sum a_i^2 + \sum a_i2d+id^2\)
放左边：\(f_{i,j+d_i\times i} \gets f_{i-1,j} + 2j\times d_i + i\times d_i^2\)
时间复杂度 \(O(V \times n)\)。
b6e6 - NFLSOJ，有点问题
序列变换问题，DP
对于序列直接转化，步数是一个经常讨论的问题，那么对于两个状态之间的步数，就是 \(\sum abs(dist(pos_{1原}-pos_{1现}))+abs(dist(pos_{0原}-pos_{0现})) >> 1\)（即所有的正数之和）。
然后就是贡献，发现贡献可以由 \(cnt_{pre0}\) 表示。
设计状态 \(dp_{i,j,k}\) 表示前 \(i\) 个数，有 \(j\) 个 \(0\)，差值为正数 \(k\) 之和，得到的价值最大值。
注意步数的浪费。
B. Integers Have Friends - 暑期训练37，E. 小 ω 的仙人掌 - 暑期训练37
trick：对于需要双指针维护不可差分信息（gcd，背包等），考虑维护两个栈，\(l\) 到 \(mid\)，\(mid+1\) 到 \(r\)，动态维护并定期重构。
B 题是维护 gcd。E 题要稍微转化一下，其实就是一个 \(0/1\) 背包，最后看 \(dp[w]\) 是否 \(\le k\)。代码细节有点多。
C. 疯狂传染病 - 暑期训练37
因为乘法的结合律，可以使用倍增，直接 c[i*j%mod]|=a[i]&b[j] ；也有找循环节的做法（也许是数据太水）；或者 \(dp_{i,j,k}\) 表示经过 \(2^k\) 天，初始 \(j\) 被感染，最后有哪些会被感染。
从数据范围上出发：类似矩阵快速幂；从性质上出发：可结合的信息转移。
D. 小C的屏幕保护程序 - 暑期训练37、全民健身[NFLS]
参变分离
\(ans = \sum calc(i,x)\)，其中 \(calc(i,x)\) 为 \((i,i+1)\) 这一段。对于不同的询问高度会分为三段，维护将参数提出来，用数据结构维护多项式的系数即可。还有一种方法是 \(n * h\) 刚好的复杂度，每次修改单点。但是有一个卡时间的做法是，对于每次修改，直接扫过来维护每个高度的答案。
全民健身这道题目，当时没算空间，浪费了大把时间。主要是一个 \(dp\)，然后发现式子，参变搞一下是关键。
字符串匹配度
正确的状态有利于发现正解的突破口（即使时间复杂度更劣），贡献转换（题意转换）
一开始设计了状态 \(dp_{i,j}\) 进行统计，\(s1,s2\) 是分开的。但实质上这就是一个 \(LCS\)，暴力的状态改为 \(dp_{i,p,q}\) 表示枚举左端点 \(l\) 到第 \(i\) 个位置，匹配到 \(p,q\) 的方案数。虽然时间复杂度更劣了，但是这就促使我们发现每次转移的初值只不过是 \(dp_{l,0,0}\) 加了 \(1\)。那么就不用枚举左端点 \(l\)，直接“加入”左端点即可，每次加入答案。
其实题面就是绕了一下，刻意地应当被引导到 \(LCS\) 上去。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;
int n,l1,l2;
char a[N],s1[N],s2[N];
vector<int> e1[30],e2[30];
int f[30][30],ans;
inline int add(int x,int y){ return x + y >= mod ? x + y - mod : x + y; }
inline void toadd(int &x,int y){ x = add(x,y); }
int main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
scanf("%s%s%s",a+1,s1+1,s2+1);
n = strlen(a+1), l1 = strlen(s1+1), l2 = strlen(s2+1);
for(int i = l1;i;--i)e1[s1[i]-'a'].push_back(i);
for(int i = l2;i;--i)e2[s2[i]-'a'].push_back(i);
for(int i = 1;i<=n;++i){
toadd(f[0][0],1);
for(int x : e1[a[i]-'a'])for(int y = 0;y<=l2;++y)toadd(f[x][y],f[x-1][y]);
for(int x : e2[a[i]-'a'])for(int y = 0;y<=l1;++y)toadd(f[y][x],f[y][x-1]);
toadd(ans,f[l1][l2]);
}
printf("%d",ans);
return 0;
}