LOJ2966
考虑区间 \(dp\)，\(dp_{l,r,p}\) 表示当前区间 \([l,r]\)，删到只剩下 \(p\) 个相同的数。\(f_{l,r}\) 表示将区间 \([l,r]\) 删空的代价。
考虑转移，我们先枚举 \(dp_{l,r,p}\) 由 \([l,x]\) 转移来，那么一定是 \(p-1\) 个，而 \(r\) 是第 \(p\) 个。这就要求 \(c_x\) 和 \(c_r\) 相等。
然后，枚举 \(f_{l,r}\) 是从连续几个转移来，转移代价是 \(\max\{0,k-p\}\)。
最后，\(f_{l,r}\) 也可能是断开区间分别删，枚举断点。
复杂度 \(O(n^4)\)。
DP N
考虑区间 \(dp\)，设 \(dp_{l,r}\) 表示将区间 \([l,r]\) 合并成 \(s_r-s_{l-1}\) 的最小代价。
我们只需要枚举断点然后合并即可。
CF607B
考虑区间 \(dp\)，设 \(f_{l,r}\) 表示当前将 \([l,r]\) 删的只剩一个回文串的最小代价，\(g_{l,r}\) 表示当前将 \([l,r]\) 删的只剩下一个回文串和 \(r\) 的最小代价，\(dp_{l,r}\) 表示当前将 \([l,r]\) 删空的代价。
考虑先预处理所有的回文串，判断一个 \([l,r]\) 是否回文只需要判断 \([l+1,r-1]\) 是否回文并且 \(l\) 是否和 \(r\) 相同。
然后考虑转移，\(f_{l,r}\) 一定从 \(g_{x,r}\) 转移来，并且要求 \(a_l=a_r\)，转移代价是 \(dp_{l+1,x-1}\)。\(g_{l,r}\) 一定从 \(f_{l,x}\) 转移来，转移代价 \(dp_{x+1,r-1}\)。
\(dp_{l,r}\) 可以从 \(f_{l,r}\) 转移来，也可以从 \(dp_{l,x}+dp_{x+1,r}\) 转移来。
复杂度 \(O(n^3)\)，