求调qwq
查看原帖
求调qwq
756843
Lilium_davidii楼主2024/7/21 11:36
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[200005][3][4];
int a[200005][3];
int c(int i){
    return a[i][1]+a[i][2]*2;
}
signed main(){
    int n;
    cin>>n;
    string s1,s2;
    cin>>s1>>s2;
    int all=0;
    for(int i=1;i<=n;i++){
        a[i][1]=s1[i-1]-'0';
        a[i][2]=s2[i-1]-'0';
        all+=a[i][1];all+=a[i][2];
    }
    for(int i=0;i<200005;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<4;k++){
                dp[i][j][k]=0x3f3f3f3f3f3f3f3f;
            }
        }
    }
    for(int i=0;i<4;i++){
        if((i&c(1))==i){
            dp[1][1][i]=0;
            if(i!=c(1)){
                dp[1][1][i]++;
            }
            if(i==0&&c(1)==3){
                dp[1][1][i]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=2;j++){
            for(int k=0;k<4;k++){
                if((k&c(i))==k){
                    if(k==0){
                        dp[i+1][j][c(i+1)]=min(dp[i][j][k],dp[i+1][j][c(i+1)]);
                    }else if(k==j){
                        dp[i+1][j][c(i+1)]=min(dp[i][j][k],dp[i+1][j][c(i+1)]);
                    }else{
                        if((c(i+1)&j)==j){
                            dp[i+1][j^3][c(i+1)^j]=min(dp[i][j][k]+1,dp[i+1][j^3][c(i+1)^j]);
                        }else{
                            dp[i+1][j^3][c(i+1)]=min(dp[i][j][k],dp[i+1][j^3][c(i+1)]);
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<4;i++){
        ans=max(ans,all-min(dp[n+1][1][i],dp[n+1][2][i]));
    }
    cout<<ans;
    return 0;
}

WA on #11 输出188,答案190

2024/7/21 11:36
加载中...