难度是 \(1900\sim 2600\)。
1132F Clear the String *2000
区间 \(\text{dp}\)，设 \(f_{l,r}\) 为删去区间 \([l,r]\) 的最小代价。
一个子问题的突破点是讨论 \(l\) 是怎么被删去的，最基本的删去方法：
\[f_{l,r}=f_{l+1,r}+1 \]如果区间 \((l,r]\) 中存在一个 \(i\) 满足 \(s_l=s_i\)，那么可以把 \((l,i)\) 的都删去之后按照删 \([i,r]\) 的方法删，删 \(i\) 的时候带上 \(l\) 即可。
\[f_{l,r}=\min_{l<i\le r,s_l=s_i} \{f_{l+1,i-1}+f_{i,r}\} \]1107E Vasya and Binary String *2400
做上一道是为了这一道。
有了一个价值，依然是关心 \(l\) 是怎么删去的，增加一维 \(f_{l,r,k}\) 表示 \(l\) 同 \([l,r]\) 中与其相等的累计 \(k\) 个一起删去，定义 \(f_{l,r,0}\) 位 \(f_{l,r,k}\) 的的最大值。
仿照上面的转移，最基本的是：
\[f_{l,r,1}=f_{l+1,r,0}+a_k \]枚举相等位置 \(i\)，这里要删去 \(k-1\) 个元素一起删去的贡献：
\[f_{l,r,k}=\max_{l<i\le r,s_l=s_i}\{f_{l+1,i-1,0}+f_{i,r,k-1}-a_{k-1}+a_k\} \] 标签：String,乱写,CodeForces,删去,杂题,dp From： https://www.cnblogs.com/SoyTony/p/dp_Problems_on_CodeForces_1.html