题目描述
题解
显然是一个区间DP，最直观的思路就是设置状态 f [ l ] [ r ] f[l][r] f[l][r]为区间 [ l , r ] [l,r] [l,r]的最高得分。
但是对于中间消除以后再消边上操作会十分困难，我们这里采用一种费用提前计算的方法：
我们设 f [ l ] [ r ] [ k ] f[l][r][k] f[l][r][k]表示在区间 [ l , r ] [l,r] [l,r]消完以后，还要消在 r r r右边颜色和 r r r一样的 k k k个的方案数。
我们可以用这幅图来诠释这个状态转移方程。
第一种情况，若 r r r不能与 r ? 1 r-1 r?