Part 1. 动态规划
Part 1.1 区间 dp
1.1.1 P7914
这是一个练手题。我们先来说说括号序列计数的一个简单 trick。
首先，区间 dp 的常见做法是枚举中间的“隔板”进行转移。但是遇到计数时，如果括号序列是 ()()()() 这个鬼样子，那么就有三个点可供枚举，即算重了。
我们考虑一个计数的原则：不重时，考虑“第一”原则：对于当前区间左端点，若合法则必然是左括号。找到与之匹配的右括号转移，那么这个右括号具有唯一性，即可转移。
具体的，设 \(f(i,j)\) 表示区间内的总合法方案数；\(g(i,j)\) 表示 \(i\) 与 \(j\) 匹配，且合法的方案数。
转移（大概）：\(g(i,j) = f(i+1,j-1)\)；\(f(i,j)=\sum{g(i,k)f(k+1,j)}\)
关于原题的转移，换汤不换药。
1.1.2 CF888F
这个环，假的。我们把 \(1\) 和 \(n\) 这条边放在最底下看，是不是就不需要看环了？\(1\) 和 \(n\) 这条边不可能与其他边相交。
然后，由于这个线段相交的限制，我们自然能想到区间 DP。设 \(f(i,j)\) 表示区间内能成树的方案数。
不妨考虑上面的想法，枚举一个点 \(k\)，然后链接 \(i,k\)，看看发生了什么——区间裂开了。现在变成了 \([k,j]\) 这个区间内部链接，\([i,k]\) 这个区间内部链接的方案数乘积。
但是 \([i,k]\) 强制相连，故考虑设 \(g(i,j)\) 表示 \(i,j\) 相连的方案数（要什么求什么的想法，此时可能用到相同套路） 可以找到中转点 \(k\)，转移为 \(f(i,k) \times f(k+1,j)\)，显然不会算重。
1.1.3 P5851
考虑区间 \([i,j]\) 内最后一个吃到 pie 的奶牛，则至少给它留一个。设留下的 pie 在 \(k\) 处。则，我们需要找到过 \(k\) 且在 \([l,r]\) 区间内的最大权奶牛，并把 pie 给它吃。剩下的为了保证这个奶牛有的吃，不会碰到 \(k\)，则划分为两个独立区间，实现了转移。
很妙的思路，且保证了不会算重（模拟易发现）。如果考虑奶牛顺序，必然是死路一条。
1.1.4 AT_abc261_g
考虑把 \(S \to T\) 变成 \(T \to S\)（关键，看条件单个字符变成字符串，倒着考虑更好），那么我们考虑区间 DP 搞出来 \(f(i,j,c)\) 表示区间 \([i,j]\) 变成字符 \(c\) 的最小步数。最后线性 DP 合并。
具体的，枚举 \([i,j]\)，枚举规则，内部再匹配规则，时间复杂度高达 \(\mathcal{O}(n^6)\)。
我卡死在了这里。事实上，我们枚举了两次区间，内部匹配的记录可以是大家公用的一个数组，而不是每个区间都重造。
我们考虑设计一下：\(g(i,j,k,l)\)，区间 \([i,j]\) 在第 \(k\) 条规则匹配到了第 \(l\) 个字母的最小方案数。这个的转移也是比较容易的。
唯一的恶心细节在于单个字符之间的变换。这里我们每次合并完以及初始化时最短路乱搞一下即可，复杂度不会炸的。\(\mathcal{O}(n^5)\)。
1.1.5 P5985
不如先观察观察性质再做！我们发现，上升序列的 popcount 不好对当前的单个数进行维护。但是，我们观察最高位的 popcnt，必然是一段 0 和一段 1！这启发我们，先考虑 \(m = 2^k -1\) 时候的做法。
我们可以很容易胡出来一个区间 DP：\(f(i,j,c)\) 表示 \([i,j]\) 区间内，范围在 \([0,2^c)\) 的方案数。枚举中间点 \(k\) 转移即可。注意，我们允许 \(k=i-1\) 和 \(k=j\)，两边都可以是空区间。
然后就是处理 \(m\) 不是 \(2^k-1\) 的情况。相信你也看到了为了处理方便，我们不妨令 \(m’ = m+1\)。
比如，对于 \(m'=10=(1010)\)，我们拆分成 \([0,8)\) \([8,10)\)（按位拆成一堆段），你会发现第 \(x\) 段等于是前面几位有强制的 popcount 贡献，后面几位任意，等价于 \([0,2^c)\) 范围内的处理。为了直观，放一下代码。
ll n,m,a[205];
ll f[64][205][205], g[64][205];
void solve(){
n=read(), m=read()+1;
for(ll i=1;i<=n;i++) a[i]=read()+a[i-1];
for(ll i=0;i<64;i++)
for(ll j=0;j<205;j++)
for(ll k=0;k<205;k++) f[i][j][k]=-1e17;
for(ll i=1;i<=n+1;i++) f[0][i][i] = f[0][i][i-1] = 0;
for(ll bit=1;bit<=62;bit++){
for(ll i=1;i<=n+1;i++)
f[bit][i][i-1]=0;
for(ll len=1;len<=n;len++)
for(ll i=1,j=len;j<=n;i++,j++){
for(ll k=i-1;k<=j;k++)
f[bit][i][j] = maxx(f[bit-1][i][k] + f[bit-1][k+1][j] + a[j] - a[k], f[bit][i][j]);
}
}
vector<ll>vec;
for(ll i=62;i>=0;i--)
if(m & (1ll<<i)) vec.push_back(i);
ll sz=vec.size();
for(ll i=0;i<64;i++)
for(ll j=0;j<205;j++) g[i][j]=-1e17;
g[0][0] = 0;
for(ll i=0;i<sz;i++)
for(ll j=0;j<=n;j++)
for(ll k=0;k<=j;k++){
g[i+1][j]=maxx(g[i][k] + f[vec[i]][k+1][j] + i * (a[j] - a[k]), g[i+1][j]);
}
printf("%lld\n", g[sz][n]);
}
1.1.7 感谢我校 dalao 的贡献
给你一个 \(n \times m\) 的矩阵，第 \(i\) 行表示一个序列 \(a_i\)，长度为 \(m\)。
现在你要维护一个栈（初始是空的），可以进出栈顶元素（即序列的末尾）
共有 \(n\) 天，每天你都要把栈变成和 \(a_i\) 相等的样子。
最后一天结束后，你需要把栈清空。
求最小操作次数。
数据范围：\(n,m \le 100\)。
考虑对于区间 \([i,j]\)，从空栈开始满足这些天的需求，最后清空的方案数。
贪心，我们一定会将 \([i,j]\) 内的公共部分留在栈底，然后枚举中间点转移即可。
Part 1.2 数位 DP（杂题选）
1.2.1 CF1670F Jee, You See?
逆天神题，被当时的我想出来了。
经典地，拆成 \(ans(r) - ans(l-1)\)。对于 \(\sum \le r\) 的限制，我们可以记录一个余量，从高位往低位看，根据余量得出这一位能选几个数填 \(1\)。
但是余量太大，寄了。我们考虑维护余量除以当前位权，这才是我们真正想要的。如果 \(r\) 的这一位是 \(1\)，那么这个值可以多 \(1\)。等到更低一位时，还没用掉的余量就会 \(\times 2\)。
这样做有什么好处吗？如果当前的余量过大，超过 \(2048\)，即使每次用掉 \(n\)，下一次也会 \(\times2\)，也就是说已经任意取了。问题迎刃而解。
1.2.2 CF1710C XOR Triangle
$a \oplus b + b \oplus c \ge a \oplus c $，可以按位证明。
会寄的情况是取到 \(1\) 个等号。
按位考虑，只要做到对于三个式子都有一位取到大于号，条件就成立了。
1.2.3 P7961 NOIP2021 T2
和 CF1670F 很像，也是对于余量的考虑。
这个 trick 叫做 数位背包。
Part 1.3 树形 DP
Part 1.3.1 简单题
1.3.1.1 ABC287F
树上背包的模板。
设 \(f(0/1, i, j)\) 表示第 \(i\) 个点内有 \(j\) 的联通块，\(i\) 这个点选或不选的方案数。
重点：
- 复杂度，其实是 \(\mathcal{O}(n^2)\) 的，上下界优化即可。
- 转移的时候最好开一个新的数组避免冲突。
void treedp(ll x,ll fa){
sz[x]=1;
for(auto y: E[x]){
if(y==fa) continue;
treedp(y,x);
}
// 这个点不选
f[0][x][0]=1;
for(auto y: E[x]){
if(y==fa) continue;
memset(temp, 0, sizeof(temp));
for(ll j=sz[x]; j>=0; j--)
for(ll k=sz[y]; k>=0; k--){
temp[j+k] = (temp[j+k] + f[0][x][j] * (f[1][y][k] + f[0][y][k]) % mod) % mod;
}
sz[x] += sz[y];
for(ll i=0;i<=sz[x];i++) f[0][x][i] = temp[i];
}
// 这个点选
sz[x] = 1, f[1][x][1]=1;
for(auto y: E[x]){
if(y==fa) continue;
memset(temp, 0, sizeof(temp));
for(ll j=sz[x]; j>=0; j--)
for(ll k=sz[y]; k>=0; k--){
temp[j+k] = (temp[j+k] + f[1][x][j] * f[0][y][k] % mod) % mod;
temp[j+k-1] = (temp[j+k-1] + f[1][x][j] * f[1][y][k] % mod) % mod;
}
sz[x] += sz[y];
for(ll i=0;i<=sz[x];i++) f[1][x][i] = temp[i];
}
}