题解 | #子序列#

在队首插入a或在队尾插入b，求一下最大值，如此简单
手残，用了15分钟

#include<bits/stdc++.h>
using namespace std;
char a[5500005];
int dp1[5500005],dp2[5500005];
unsigned long long ans1,ans2;
int main(){
    scanf("%s",a+1);
    int n=strlen(a+1);
    dp1[0]=1,dp2[n+1]=0;
    for(int i=1;i<=n;i++){
        if(a[i]=='a')dp1[i]=dp1[i-1]+1;
        else dp1[i]=dp1[i-1];
    }
    for(int i=n;i>=1;i--){
        if(a[i]=='b')dp2[i]=dp2[i+1]+1;
        else dp2[i]=dp2[i+1];
    }
    for(int i=1;i<=n;i++){
        if(a[i]=='a')ans1+=dp1[i-1]*dp2[i+1];
    }
    dp1[0]=0,dp2[n+1]=1;
    for(int i=1;i<=n;i++){
        if(a[i]=='a')dp1[i]=dp1[i-1]+1;
        else dp1[i]=dp1[i-1];
    }
    for(int i=n;i>=1;i--){
        if(a[i]=='b')dp2[i]=dp2[i+1]+1;
        else dp2[i]=dp2[i+1];
    }
    for(int i=1;i<=n;i++){
        if(a[i]=='a')ans2+=dp1[i-1]*dp2[i+1];
    }
    cout<<max(ans1,ans2);
    return 0;
}