[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];
}