[CQOI2007]涂色PAINT

[CQOI2007]涂色PAINT

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。
每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。
例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。 输入描述:
输入仅一行，包含一个长度为n的字符串，即涂色目标。 字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

输出描述:

仅一行，包含一个数，即最少的涂色次数。

示例1
输入
复制

AAAAA

输出
复制

1

示例2
输入
复制

RGBGR

输出
复制

3

题解：

和小小粉刷匠这个题很像
区间dp先记住固定模板

/*
dp[i][j]是从1到n
初始化dp[i][i]=1,或者其他的
*/
for(int len=2; len<=n; len++){//枚举长度
        for(int i=1; i<=n; i++){//枚举起点i
            int j=i+len-1;//枚举终点j
            if(j > n) break;
            for(int k=i; k<j; k++){//找断点k的位置,可随实际情况修改
            //将区间[i,j],拆成[i,k][k+1,j]
                ......
            }
        }
    }

dp先初始化
注意题意，我们可以刷区间[i,j]，当s[i] = = s[j]时，这样就可以省一步
所以有
if s[i] == s[j]
dp[i][j]=min(dp[i][j],dp[i+1][j],dp[i][j-1],dp[i+1][j-1]+1)
从第二个往后分别是：第i位可以省一步，或者第j位省一步，或者第i位和第j位都省了然后加1.（最后这个dp[i+1][j-1]+1其实可以省略）
else （如果不相等）
我们就更新当前区间[i，j]
dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+7;
int dp[100][100];
char s[100];
int main()
{

    cin>>(s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)
    {
        dp[i][i]=1;
    }
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=n;i++)
        {
            int j=i+len-1;
            dp[i][j]=dp[i+1][j]+1; 
            if(j>n)break;
            if(s[i]==s[j])
            {
                dp[i][j]=min(dp[i][j],dp[i+1][j]);
                dp[i][j]=min(dp[i][j],dp[i][j-1]);
                dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1);
            }
            else 
            for(int k=i+1;k<=j;k++)
            {
                dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);
            }
        }
    }
    cout<<dp[1][n];
}