CF1572C Paint 做题记录

给定长度为 $n$ 的颜色序列 $a_i$，每次你可以选择任意长度的连续且颜色相同的一段位置，将其全部变成任意同一种颜色，问你最少总共需要多少次操作才能使得整个序列颜色相同。

限制： 每一种颜色初始时在序列中最多只有20个位置（是该种颜色）。

$n\le 3000$，$a_i \le n$，$\sum n \le 3000$。

首先不难发现连续一段相同的颜色的格子可以缩成一个格子，那么不妨先缩到相邻的两个格子颜色不同。

考虑某一段格子 $[l,r]$ 最后被涂成的颜色，显然若 $[l,r-1]$ 涂的颜色和 $a_r$ 不同则需要花费一次操作把 $[l,r-1]$ 涂成 $a_r$，或者把 $r$ 涂成 $[l,r-1]$ 的颜色。那么不妨钦定让 $[l,r-1]$ 涂成 $a_r$，则可以设 $dp_{l,r}$ 表示 $[l,r]$ 这一段全部涂成 $a_r$ 所需的最小操作次数，那么有转移：

$dp_{l,r}=\min\begin{cases}dp_{l,r-1}+1\\dp_{l,k}+dp_{k+1,r}&a_k=a_r\end{cases}$

由于每种颜色出现次数最多只有 $20$，所以可以预处理出每个位置前面最后一个与它颜色相同的位置来转移，时间复杂度 $O(20n^2)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=3005;

int n,a[S];
int m,b[S],dp[S][S];
int pos[S],pre[S];

inline void slove()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	m=0;
	for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) b[++m]=a[i];
	for(int i=1;i<=n;i++) pos[i]=0;
	for(int i=1;i<=m;i++)
	{
		pre[i]=pos[b[i]];
		pos[b[i]]=i;
	}
	for(int i=1;i<=m;i++) for(int j=i;j<=m;j++) dp[i][j]=1e8;
	for(int i=1;i<=m;i++) dp[i][i]=0;
	for(int len=2;len<=m;len++)
	{
		for(int l=1;l<=m-len+1;l++)
		{
			int r=l+len-1;
			dp[l][r]=dp[l][r-1]+1;
			for(int k=pre[r];k>=l;k=pre[k])
			{
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
			}
		}
	}
	printf("%d\n",dp[1][m]);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}