洛谷 P1203

题目链接

分析

求出 $fR$ 和 $fB$ 分别表示颜色 $R,B$ 的数量前缀和，$bR$ 和 $bB$ 分别表示颜色 $R,B$ 的数量后缀和，可以用 dp，枚举断点，$d{p}_i$即为 $\max (f{R}_i,f{B}_i)+\max (b{R}_i,b{B}_i)$，最后取最大值即可。

代码

#include <bits/stdc++.h>
#define debug puts("Y")

using namespace std;

const int N = 700;
string s;
int n, fR[N], fB[N], bR[N], bB[N]; 

int main(){
	cin >> n >> s;
	s = " " + s + s;
	for(int i = 1; i <= 2 * n; i ++){
		if(s[i] == 'w'){
			fR[i] = fR[i - 1] + 1, fB[i] = fB[i - 1] + 1;
		}else if(s[i] == 'r'){
			fR[i] = fR[i - 1] + 1;
		}else{
			fB[i] = fB[i - 1] + 1;
		}
	} 
	for(int i = 2 * n; i >= 1; i --){
		if(s[i] == 'w'){
			bR[i] = bR[i + 1] + 1, bB[i] = bB[i + 1] + 1;
		}else if(s[i] == 'r'){
			bR[i] = bR[i + 1] + 1;
		}else{
			bB[i] = bB[i + 1] + 1;
		}
	} 
	int maxn = -1e9;
	for(int i = 1; i <= 2 * n - 1; i ++){
		maxn = max(maxn, 
										max(fR[i], fB[i]) + max(bR[i + 1], bB[i + 1]));
	}
	cout << (maxn > n ? n : maxn) << "\n";
	return 0;
}
/*

*/