题意:
数据范围:|串|<=1e5
解法:
d[i][0]表示第i位不修改能取得的最大值.
d[i][1]表示第i位不修改,但是前面存在修改能取得的最大值.
d[i][2]表示第i位修改能取得的最大值.
d[i][0]可以由d[i-1][0]转移,
d[i][1]可以由d[i-1][1],d[i-1][2]转移,
d[i][2]可以由d[i-1][2],d[i-1][0]转移,
code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e6+5;
int d[maxm][3];
char s[maxm];
int n;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
cin>>(s+1);
d[1][0]=d[1][1]=d[1][2]=1;
for(int i=2;i<=n;i++){
//d[i][0]表示第i位不修改能取得的最大值.
d[i][0]=d[i-1][0]+(s[i]!=s[i-1]);
//d[i][1]表示第i位不修改,但是前面存在修改能取得的最大值.
d[i][1]=d[i-1][1]+(s[i]!=s[i-1]);
d[i][1]=max(d[i][1],d[i-1][2]+(s[i]==s[i-1]));
//d[i][2]表示第i位修改能取得的最大值.
d[i][2]=d[i-1][2]+(s[i]!=s[i-1]);
d[i][2]=max(d[i][2],d[i-1][0]+(s[i]==s[i-1]));
}
cout<<max(d[n][0],max(d[n][1],d[n][2]));
return 0;
}