大家好，下面讲的题目一个都不会，但是我脸皮很厚，所以分享给大家了。
搁前面说一句：做题的时候能不能别丢掉这个算法啊！试一下啊！
Pro.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)}\)
关于原题的转移，换汤不换药。
Pro.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)\)，显然不会算重。
Pro.3 P5851
喵喵题。
考虑区间 \([i,j]\) 内最后一个吃到 pie 的奶牛，则至少给它留一个。设留下的 pie 在 \(k\) 处。则，我们需要找到过 \(k\) 且在 \([l,r]\) 区间内的最大权奶牛，并把 pie 给它吃。剩下的为了保证这个奶牛有的吃，不会碰到 \(k\)，则划分为两个独立区间，实现了转移。
很妙的思路，且保证了不会算重（模拟易发现）。如果考虑奶牛顺序，必然是死路一条。
Pro.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)\)。
Pro.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]);
}
Pro. 6 感谢我校 dalao 的贡献
给你一个 \(n \times m\) 的矩阵，第 \(i\) 行表示一个序列 \(a_i\)，长度为 \(m\)。
现在你要维护一个栈（初始是空的），可以进出栈顶元素（即序列的末尾）
共有 \(n\) 天，每天你都要把栈变成和 \(a_i\) 相等的样子。
最后一天结束后，你需要把栈清空。
求最小操作次数。
区间 DP。（废话）
可不是废话，希望大家能好好想想这题。暂时不公布 sol。如果有想法欢迎分享。
方便起见，数据范围：\(n,m \le 100\)。（够良心了）
标签：11,选讲,我们,Trick,枚举,区间,考虑,转移,DP From： https://www.cnblogs.com/BreakPlus/p/17063037.html