【CF 603A Alternative Thinking】解题报告(动态规划)

题意简述

有一个长度为 \(n\) 的 01 串 \(s\),可以选择一段区间取反(\(1\) 变 \(0\),\(0\) 变 \(1\)),求最大可能的 \(01\) 交替出现的子序列(不一定连续)长度。

题解

我们发现对于当前点,相对选择的区间来说无非就是三种位置关系(x 表示当前点,[] 表示取反区间):

  • 第一类:x...[...]
  • 第二类:[...]...x
  • 第三类:[...x...]

拆分子问题为 \(1\sim i\) 的前缀,对应上面三种情况的答案。分别设为 \(dp_{i,[0/1/2]}\)。

初始状态是 \(dp_{1,[0/1/2]}=1\),因为不管第一个数取不取反,它本身都是一个 \(01\) 交替出现的子序列。

我们推转移方程,如果 \(s_i = s_{i-1}\),第一类的话只能从上一个位置直接转移,第二类分上一个数是否在取反区间里讨论取最大值,第三类同理,得到如下式子:

\[\begin{cases} dp_{i,0}=dp_{i-1,0}\\ dp_{i,1}=\max\{dp_{i-1,1},dp_{i-1,2}+1\}\\ dp_{i,2}=\max\{dp_{i-1,0}+1,dp_{i-1,2}\}\\ \end{cases} \]

类似地,当 \(s_i\ne s_{i-1}\) 时的转移方程如下:

\[\begin{cases} dp_{i,0}=dp_{i-1,0}+1\\ dp_{i,1}=\max\{dp_{i-1,1}+1,dp_{i-1,2}\}\\ dp_{i,2}=\max\{dp_{i-1,0},dp_{i-1,2}+1\}\\ \end{cases} \]

最终的答案即为 \(\max\{dp_{n,0},dp_{n,1},dp_{n,2}\}\)。

参考代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
using namespace std;
typedef long long ll;
const int N = 1e5+5;

int n, dp[N][3];
char s[N];
template<typename T> void chkmin(T &x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T &x, T y) {if(x < y) x = y;}

int main() {
	/*
	 * 0 for x...[...]
	 * 1 for [...]...x
	 * 2 for [...x...]
	**/
	scanf("%d%s", &n, s+1);
	dp[1][0] = dp[1][1] = dp[1][2] = 1;
	rep(i, 2, n) {
		if(s[i] == s[i-1]) {
			dp[i][0] = dp[i-1][0];
			dp[i][1] = max(dp[i-1][1], dp[i-1][2]+1);
			dp[i][2] = max(dp[i-1][0]+1, dp[i-1][2]);
		}
		else {
			dp[i][0] = dp[i-1][0] + 1;
			dp[i][1] = max(dp[i-1][1]+1, dp[i-1][2]);
			dp[i][2] = max(dp[i-1][0], dp[i-1][2]+1);
		}
	}
	int ans = max(max(dp[n][0], dp[n][1]), dp[n][2]);
	printf("%d\n", ans);
	return 0;
}
上一篇:comp1531-软件工程(一)代码设计原则


下一篇:【Android Developers Training】 72. 缩放一个视图