Codeforces603 A.Alternative Thinking（dp）

题意：

数据范围：|串|<=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;
}

---

本文地址：https://blog.csdn.net/weixin_44178736/article/details/110677418