可以区间dp，但是复杂度太高。

所以应该是贪心，怎么贪心呢？

这种题目，最好还是手玩找一些规律。

可以发现，由于保证可以m次填完，所以颜色之间没有相互包含关系。

比较像分治的模型。

所以考虑拿到一个区间怎么处理。

假设a[l]==a[r]，那么为了合法，一定先刷这种颜色。然后分部分递归下去。

否则，对于区间：AEEGEABBBCDDC

里面的夹心肯定不能先处理了，可以大概看做：A..AB..BC..C

先刷哪一个？

刷两边长度较小的一个

证明：

如果刷中间，那么中间的位置之后就不能再动了。如果刷比较长的一个，那么之后不能再动。

如果刷比较短的一个，长的可以再多刷几次，贡献更大。

比较即可。（如果两边长度相同，比较下一个。）

O(m^2+n)

理论上可以后缀数组优化到：O(mlogn+n)

#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=1e5;const int M=5005;int st[M],nd[M];ll ans;int a[N];int n,m;vector
      
       mem[M];void sol(int l,int r){    //cout<<" sol "<
       
        <<" "<
        
         <<" "<
         
          <
          
           r) return; if(l==r){ ++ans;return; } if(a[l]==a[r]){ ans+=r-l+1; int las=l; for(reg i=1;i
           
            nd[a[R]]-st[a[R]]+1){ go=r;break; } L=nd[a[L]]+1;R=st[a[R]]-1; if(L>R) go=l; } if(go==l){ int las=l; for(reg i=1;i
           
          
         
        
       
      
     

总结：

没有想到的原因是，还是没有从手玩找规律这个方向入手。

对于一些没有什么思路的题，可以尝试“不完全归纳”

其实规律还是比较简单的。