A Color Game(区间dp)

来源：The 2020 ICPC Asia Taipei-Hsinchu Site Programming Contest
链接：https://codeforces.com/gym/102835/problem/E
对这些颜色进行分块是比较显然的操作，dp[i][j][q]维护在[i,j]这段区间只剩下q能最多剩多少个，用区间dp来更新，需要注意的是，如果i与j的种类相同，那么dp[i][j][q]可以用dp[i+1][j-1]+a[i]+a[j]来更新，初始把dp[i][j][q]都赋为-1即可，代表i，j不能只剩下q。比较麻烦的是维护和初始化。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f
#define fi first
#define se second
char s[510];
int m,n,b[510],dp[510][510][10],sz;
map<char,int> mp;
map<int,pair<int,int> >d;
void init(){
    mp['R']=1;
    mp['G']=2;
    mp['B']=3;
    mp['C']=4;
    mp['M']=5;
    mp['Y']=6;
    mp['K']=7;
}
int main(){
    scanf("%s",s+1);
    scanf("%d",&m);
    init();
    n=strlen(s+1);
    for(int i=1;i<=n;++i) b[i]=mp[s[i]];
    for(int i=1;i<=n;++i){
        if(b[i]!=b[i-1]) d[++sz]=make_pair(b[i],0);
        d[sz].se++;
    }
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=sz;++i){
        dp[i][i][d[i].fi]=d[i].se;
        for(int j=1;j<=7;++j){
            if(d[i].se>=m){
                if(j==d[i].fi) continue;
                dp[i][i][j]=0;
            }
        }
    }
    for(int l=2;l<=sz;++l){
        for(int i=1;i+l-1<=sz;++i){
            int j=i+l-1;
            for(int k=i;k<j;++k){
                for(int q=1;q<=7;++q){
                    if(dp[i][k][q]==-1||dp[k+1][j][q]==-1)continue;
                    dp[i][j][q]=max(dp[i][j][q],dp[i][k][q]+dp[k+1][j][q]);
                }
            }
            int col = d[i].fi;
            if(d[i].fi==d[j].fi&&dp[i+1][j-1][col]!=-1)
            {
                dp[i][j][col]=max(dp[i][j][col],dp[i+1][j-1][col]+d[i].se+d[j].se);
            }
            for(int q=1;q<=7;++q){
                if(dp[i][j][q]>=m)
                {
                    for(int p=1;p<=7;++p){
                        if(dp[i][j][p]==-1) dp[i][j][p]=0;
                    }
                    break;
                }
            }
        }
    }
    for(int q=1;q<=7;++q){
        if(dp[1][sz][q]>=m){
            printf("Yes\n"); return 0;
        }
    }
    printf("No\n");
    return 0;
}