[CQOI2007]涂色PAINT | 区间dp

考虑区间dp即可

我们可以发现在左右端点颜色相同的时候
越在外面的颜色越早涂是最好的
例如：RGR
先涂R比先涂G好

根据上述情况 很容易发现 ：
当左右端点颜色一致时 只需要扩充即可 不需要在涂色了 因为涂的颜色已经早涂了
如果颜色不一致 ，就是区间dp的套路 ，枚举从哪个中间点分开

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=1e6+10;
const int maxn =1e7+10;
const int mod= 1e9+7;
const int Mod = 1e6+7;
///const double eps=1e-10;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll dp[1005][1005];
char s[maxn];
int main()
{
    scanf("%s",s+1);
    int len = strlen(s+1);
    for(int i=1;i<=len;i++){
        for(int k=1;k<=len;k++){
            dp[i][k] = INF;
        }
    }
    for(int i=1;i<=len;i++) dp[i][i] = 1;
    for(int l=1;l<=len;l++){
        for(int i=1;i+l<=len;i++){
            int e = i+l;
            if(s[i] == s[e]) dp[i][e] = min(dp[i][e],min(dp[i+1][e],dp[i][e-1]));
            else{
                for(int k=i;k<=e-1;k++)
                    dp[i][e] = min(dp[i][e],dp[i][k]+dp[k+1][e]);
            }
        }
    }
    printf("%lld\n",dp[1][len]);
    return 0;
}
/**
1000

**/