考虑dp dp[0]为未反转的,dp[1]当前正在反转,dp[2]已经反转完成的最大值。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e5+10; int n,dp[N][3]; char str[N]; signed main(){ scanf("%d %s",&n,str+1); for(int i=1;i<=n;i++){ dp[i][0]=dp[i-1][0]+(str[i]!=str[i-1]); dp[i][1]=max(dp[i-1][0]+(str[i]==str[i-1]),dp[i-1][1]+(str[i]!=str[i-1])); dp[i][2]=max(dp[i-1][2]+(str[i]!=str[i-1]),dp[i-1][1]+(str[i]==str[i-1])); } cout<<max(max(dp[n][0],dp[n][1]),dp[n][2]); return 0; }