题解 | #[CQOI2007]涂色PAINT#

理解题目

首先，我们需要清楚地理解题目要求。我们有一个长度为 $n$ 的木版，初始时没有任何颜色。我们的目标是通过最少的涂色次数，将木版涂成给定的目标颜色序列。每次涂色可以选择任意一段连续的区间，并将该区间内的所有部分涂成同一种颜色。后续的涂色会覆盖之前的颜色。

解题思路

这个问题类似于“区间动态规划”（Interval DP）的问题。我们需要找到一个状态表示和状态转移方程，以计算出最少需要多少次涂色才能达到目标。

状态定义

定义 $dp[i][j]$ 为将区间 $[i, j]$ 涂成目标颜色所需的最少涂色次数。

状态转移

考虑如何从更小的区间转移到更大的区间：

基本情况：当 $i == j$ 时，即区间长度为1，只需要涂色一次，因此 $dp[i][j] = 1$ 。

区间分割：对于区间 $[i, j]$ ，我们可以考虑以下两种情况：

情况1：如果 $s[i] == s[j]$ ，那么可以在涂 $s[i] 或 s[j]$ 的时候顺便涂另一个。因此， $dp[i][j]$ 可以从 $dp[i][j-1]$ 或 dp[i+1][j] 转移而来。

例如，RGBGR 中 $s[0] == s[4] == 'R'$ ，可以在涂 $[0,4]$ 时先涂 $'R'$ ，然后处理中间部分。

情况2：如果 $s[i] != s[j]$ ，那么我们需要将区间分成两部分，分别涂色。即 $dp[i][j] = min(dp[i][k] + dp[k+1][j])$ 对于所有 $i <= k < j$ 。

初始化

所有长度为 $1$ 的区间 $dp[i][i] = 1$

最终代码

#include <bits/stdc++.h>
#define ll long long 
#define endl "\n"
using namespace std;
const int N=50+5;
string s;
int sop;
int dp[N][N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>s;
	sop=s.size();
	for(int i=0;i<sop;i++){
		dp[i][i]=1;
	}
	for(int len=2;len<=sop;len++){
		for(int l=0;l+len-1<sop;l++){
			int r=l+len-1;
			if(s[l]==s[r]){
				dp[l][r]=dp[l+1][r];
			}else{
				dp[l][r]=INT_MAX;
				for(int k=l;k<r;k++){
					dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
				}
			}
		}
	}
	cout<<dp[0][sop-1];
	return 0;
}