技术教程 编程教程 2021.07.17 P4170 染色（区间DP） 正文

2021.07.17 P4170 染色（区间DP）

2023-05-13,,

2021.07.17 P4170 染色（区间DP）

[P4170 CQOI2007]涂色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.目标状态可以由哪些状态转移过来。

题目：

每次可以改变一段连续区间的颜色，问最少需要几次可以吧颜色改为目标区间颜色。

分析：

在一段连续区间(l,r)内，如果l,r处颜色相同，则选择(l+1,r)以及(l,r-1)这两个区间内修改次数少的，如果不同，枚举区间内断点，将两个小区间内次数相加。

代码如下：

#include<bits/stdc++.h>

using namespace std;

string a;

int f[55][55];

int main(){

	cin>>a;

	int n=a.size();

	memset(f,0x3f3f3f3f,sizeof(f));

	for(int i=1;i<=n;i++)f[i][i]=1;

	for(int l=2;l<=n;l++){

		for(int i=1;i+l-1<=n;i++){

			int end=i+l-1;

			if(a[i-1]==a[end-1]){

				f[i][end]=min(f[i+1][end],f[i][end-1]);

				continue;

			}else{

				for(int k=i;k<=end;k++){

					f[i][end]=min(f[i][end],f[i][k]+f[k+1][end]);

				}

			}

		}

	}

	cout<<f[1][n];

	return 0;

}

2021.07.17 P4170 染色（区间DP）的相关教程结束。

《2021.07.17 P4170 染色（区间DP）.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!