洛谷 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;
}
/*

*/

原文地址：https://blog.csdn.net/zc2000911/article/details/135707824

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！