[Acwing]3996. 涂色 区间DP

前言

t a g : tag : tag: 区间dp 染色问题 传送门 :

思路 : 状态表示 :

f [ i ] [ j ] f[i][j] f[i][j]表示 起点从 [ i , j ] [i,j] [i,j]当中选,最终操作成颜色都相同的最小步数

状态计算 :

如果 c [ i ] ≠ c [ j ] c[i]\neq c[j] c[i]​=c[j] f [ i ] [ j ] = f [ i + 1 ] [ j ] + 1 f[i][j] = f[i+1][j]+1 f[i][j]=f[i+1][j]+1最后扩展到 a [ i ] a[i] a[i] f [ i ] [ j ] = f [ i ] [ j − 1 ] + 1 f[i][j] = f[i][j-1]+1 f[i][j]=f[i][j−1]+1最后扩展到 a [ j ] a[j] a[j]

否则 c [ i ] = c [ j ] c[i]=c[j] c[i]=c[j] f [ i ] [ j ] = f [ i + 1 ] [ j − 1 ] + 1 f[i][j] =f[i+1][j-1]+1 f[i][j]=f[i+1][j−1]+1

因为染色操作是中间向两边进行扩展

因此当两边不相同的时候,我们考虑是将左端点染色好还是右端点进行染色好 Code：

int a[N];
int f[N][N];
int n;


void solve(){
	cin>>n;
	for(int i=0;i>a[i];
		if(i && a[i] == a[i-1]){
			i --;
			n --;//将连续的块发 进行合并操作
		}
	}
	
	//区间dp 枚举长度 和 左端点
	for(int len = 2;len