Codeforces 1114D Flood Fill (区间DP or 最长公共子序列)

清疚 2021-09-29 10:08 207阅读 0赞

题意：给你n个颜色块，颜色相同并且相邻的颜色块是互相连通的（连通块)。你可以改变其中的某个颜色块的颜色，不过每次改变会把它所在的连通块的颜色也改变，问最少需要多少次操作，使得n个颜色块的颜色相同。

例如：\[1, 2, 2, 3, 2\]需要2步：\[1, 2, 2, 3, 2\] -> \[1, 2, 2, 2, 2\] -> \[2, 2, 2, 2, 2\]。

思路：我们先把颜色块压缩（即把本来颜色相同并且相邻的颜色块合并）。容易发现，如果出现了形如\[1, 2, 3, 1\]这种情况, 那么显然先合并两个1中间的部分，再把中间部分变成1操作次数会更少，于是我们就可以得到2种思路：

法1：区间DP：设dp\[l\]\[r\]是合并\[l, r\]之间的颜色块的最小的代价，那么分两种情况：

1: l - 1和r + 1颜色相同，dp\[l - 1\]\[r + 1\] = min(dp\[l - 1\]\[r + 1\], dp\[l\]\[r\] + 1);//l - 1和r + 1颜色相同，一步就可以转移到

2: l - 1和r + 1颜色不同，dp\[l - 1\]\[r\] = min(dp\[l - 1\]\[r\], dp\[l\]\[r\] + 1);dp\[l\]\[r + 1\] = min(dp\[l\]\[r + 1\], dp\[l\]\[r\] + 1);//l - 1和r + 1颜色不同，那只能一步转移到l - 1, r或者l, r + 1

代码：

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 5010;
    int dp[maxn][maxn];
    int a[maxn], b[maxn], tot;
    int main() {
    	int n;
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i++) {
    		scanf("%d", &a[i]);
    	}
    	for (int i = 1; i <= n; i++) {
    		if(a[i] == a[i + 1]) continue;
    		b[++tot] = a[i];
    	}
    	memset(dp, 0x3f, sizeof(dp));
    	for (int i = 1; i <= tot; i++) dp[i][i] = 0;
    	for (int len = 1; len <= tot; len++) {
    		for (int l = 1; l <= tot - len + 1; l++) {
    			int r = l + len - 1;
    			if(b[l - 1] == b[r + 1]) {
    				dp[l - 1][r + 1] = min(dp[l - 1][r + 1], dp[l][r] + 1);
    			}
    			else {
    				dp[l - 1][r] = min(dp[l - 1][r], dp[l][r] + 1);
    				dp[l][r + 1] = min(dp[l][r + 1], dp[l][r] + 1);
    			}	
    		}
    	}
    	printf("%d\n", dp[1][tot]);
    }

法2：假设n个颜色块的颜色都各不相同，那么合并需要n - 1次。如果出现了\[1, 2, 3, 1\]这种情况，那么合并次数可以少一次。如果是\[4, 1, 2, 3, 4, 3, 2, 1\]这种情况，那么先合并3到3之间，再合并2到2之间，再合并1到1之间比先合并4到4之间更优。如果我们把压缩序列上相同并且相距最近的两个数看成区间，每出现一个区间答案会减一，所以答案是n - 1 - 不相交的最多的区间的数目（区间在端点相交不算相交,包含关系不算相交）。比如\[4, 1, 2, 3, 4, 3, 2, 1\]这种情况,有4个区间。4：\[1, 5\] , 1: \[2, 8\], 2: \[3, 7\], 3: \[4, 6\]。显然，保留 \[2, 8\],  \[3, 7\],  \[4, 6\]三个区间最优，答案是8 - 1 - 3 = 4。那么怎么求不相交的最多的区间的数目呢？这个区间数目是压缩序列和反向压缩序列的的LCS / 2。例如\[1, 2, 3, 1\]和\[1, 3, 2, 1\]的LCS是3，区间个数是1。为什么呢？求lCS的过程中，我们每匹配成功一次，相当于区间的左端点找到的一个可以匹配的区间的右端点，或者是一个右端点找到一个对应的左端点，而匹配过程中是一个从前往后, 一个从后往前，所以匹配成功的区间肯定不相交。这个过程之后，每个区间被算了2次，并且会匹配出一个左端点等于右端点的区间，所以要除以2。

代码：

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 5010;
    int dp[maxn][maxn];
    int a[maxn], b[maxn], c[maxn], tot;
    int main () {
    	int n;
    	scanf("%d", &n);
    	for (int i = 1; i <= n; i++) {
    		scanf("%d", &a[i]);
    	}
    	for (int i = 1; i <= n; i++) {
    		if(a[i] == a[i + 1]) continue;
    		b[++tot] = a[i];
    		c[tot] = a[i];
    	}
    	reverse(c + 1, c + 1 + tot);
    	for (int i = 1; i <= tot; i++)
    		for (int j = 1; j <= tot; j++) {
    			if(b[i] == c[j])
    				dp[i][j] = dp[i - 1][j - 1] + 1;
    			else
    				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    		}
    	printf("%d\n", tot - 1 - dp[tot][tot] / 2);
    }

转载于:https://www.cnblogs.com/pkgunboat/p/10361375.html