526互联

P4170 [CQOI2007] 涂色

发布时间 2023-11-20 11:12:28作者: 加固文明幻景

P4170 [CQOI2007] 涂色

基本思路

很容易口胡一个状态。

\(F_{l,r}\) 表示 \(ch_l\) 到 \(ch_r\) 的最小操作次数。

然而转移就开始满头大汗。

状态转移

只想到 \(F_{i,i} = 1\)

以及肯定有 \(F_{l,r} = \min(F_{l,r}, F_{l,k} + F_{k + 1, r})\)。

但是不知道什么情况用。

看了题解，果然是转移上没想出来。

对于 \(F_{l,r}\)

  • 如果 \(ch_l = ch_r\)
    • 显然从以 \(l\) 开头的 \(r-1\) 区间内的第一次涂色多涂一个就能达到当前状态。
    • \(F_{l, r} = F_{l, r- 1}\)
  • 如果 \(ch_l \neq ch_r\)
    • 不显然，枚举断点求两个子区间的和的最小值。
    • \(F_{l,r} = \min(F_{l,r}, F_{l,k} + F_{k + 1, r})\)。

因为不那么理解，我把dp每次更新时的状态都打印了下来，然后理解了原理。

对于数据：

RGBGR

这样处理

ch is not equal:F[1][1] = 1 F[2][2] = 1 F[1][2] = 2
ch is not equal:F[2][2] = 1 F[3][3] = 1 F[2][3] = 2
ch is not equal:F[3][3] = 1 F[4][4] = 1 F[3][4] = 2
ch is not equal:F[4][4] = 1 F[5][5] = 1 F[4][5] = 2
ch is not equal:F[1][1] = 1 F[2][3] = 2 F[1][3] = 3
ch is equal: F[2][4] = 2
ch is not equal:F[3][3] = 1 F[4][5] = 2 F[3][5] = 3
ch is not equal:F[1][1] = 1 F[2][4] = 2 F[1][4] = 3
ch is not equal:F[2][2] = 1 F[3][5] = 3 F[2][5] = 4
ch is not equal:F[2][4] = 2 F[5][5] = 1 F[2][5] = 3
ch is equal: F[1][5] = 3

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

char ch[56];
int n;
int F[56][56];

int main()
{
	scanf("%s", ch + 1);
	n = strlen(ch + 1);
	memset(F, 0x7f, sizeof(F));
	for (int i = 1; i <= n; i++)
	{
		F[i][i] = 1;
	}
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j + i <= n; j++)
		{
			for (int k = j; k < j + i; k++)
			{
				if(ch[j] == ch[j + i])
				{
					F[j][j + i] = F[j][j + i - 1];
					//printf("ch is equal: F[%d][%d] = %d\n",j,j+i,F[j][j+i]);
					break;
				}
				else
				{
					if (F[j][k] + F[k + 1][j + i] < F[j][j + i])
					{
						F[j][j + i] = F[j][k] + F[k + 1][j + i];
						//printf("ch is not equal:F[%d][%d] = %d F[%d][%d] = %d F[%d][%d] = %d\n",j,k,F[j][k],k+1,j+i,F[k + 1][j + i],j,j+i,F[j][j+i]);
					}
				} 
			}
		}
	}
	cout << F[1][n];
	return 0;
}