2018-ACetic_ACid/AugTrain-01/I

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include<bits/stdc++.h>

#define eb emplace_back
#define fir first
#define sec second
#define all(v) v.begin(),v.end()

#ifdef LOCAL
    #define debug 0
#else
    #define debug 0
#endif

using namespace std;
typedef long long ll;

const int N=1005,M=5005,L=12,INF=1<<30;
const int LF=0,RT=1,UP=0,DN=1;
int ld[N][L][2][2],ld0[N][L],ln[N],v[N][M];
int dp[N][L][L];
int n,m;
char ss[N][M],t[M];

inline void maxz(int& a,int b) { if(a<b) a=b; }

int main()
{
    int i,j,ans=0;
    scanf("%d%d",&n,&m);
    ans=0;
    for(i=0;i<n;i++) {
        auto s=ss[i];
        scanf("%s",s+2);
        scanf("%s",t+2);
        s[1]=s[m+2]='0';
        if(i) {
            for(j=0;j<ln[i-1];j++) {
                while(s[ld[i-1][j][DN][LF]]=='-') ld[i-1][j][DN][LF]--;
                while(s[ld[i-1][j][DN][RT]]=='-') ld[i-1][j][DN][RT]++;
            }
        }
        v[i][0]=0;
        for(j=1;j<=m+2;j++) v[i][j]=v[i][j-1]+(isdigit(s[j])?s[j]-'0':0);
        for(j=1;j<=m+2;j++) {
            if(t[j]=='|') {
                int l=ln[i]++;
                ld[i][l][UP][LF]=ld[i][l][UP][RT]=ld[i][l][DN][LF]=ld[i][l][DN][RT]=ld0[i][l]=j;
            }
        }
        for(j=0;j<ln[i];j++) {
            while(s[ld[i][j][UP][LF]]=='-') ld[i][j][UP][LF]--;
            while(s[ld[i][j][UP][RT]]=='-') ld[i][j][UP][RT]++;
        }
    }

    memset(dp,-1,sizeof(dp));
    for(i=0;i<ln[0];i++) for(j=i;j<ln[0];j++) {
        if(i==j&&ld[0][i][DN][LF]==ld[0][i][DN][RT]) maxz(ans,v[1][ld[0][j][DN][RT]]-v[1][ld[0][i][DN][LF]-1]);
        else {
            dp[0][i][j]=v[1][ld[0][j][DN][RT]]-v[1][ld[0][i][DN][LF]-1];
            maxz(ans,dp[0][i][j]);
            if(debug) printf("dp[0][%d][%d]=%d\n",i,j,dp[0][i][j]);
        }
    }
    for(i=0;i<ln[n-1];i++) ld[n-1][i][DN][LF]=1,ld[n-1][i][DN][RT]=m;
    memset(v[n],0,sizeof(v[n]));

    if(debug) {
        for(i=0;i<n;i++) {
            for(j=0;j<ln[i];j++) printf("(%d,%d|%d,%d)",ld[i][j][UP][LF],ld[i][j][UP][RT],ld[i][j][DN][LF],ld[i][j][DN][RT]);
            puts("");
        }

        for(i=0;i<=n;i++) {
            for(j=0;j<=m+2;j++) printf("%02d ",v[i][j]);
            puts("");
        }
    }
    int ul,ur,dl,dr;
    for(i=1;i<n;i++) {
        for(ul=0;ul<ln[i-1];++ul) for(ur=ul;ur<ln[i-1];++ur) {
            if(dp[i-1][ul][ur]<0) continue;
            for(dl=0;dl<ln[i];++dl) for(dr=dl;dr<ln[i];++dr) {
                if(dl==dr) {
                    if(ld[i][dl][UP][LF]==ld[i][dl][UP][RT]) continue;
                    if(ld[i][dl][DN][LF]==ld[i][dl][DN][RT]) {
                        maxz(ans,dp[i-1][ul][ur]+v[i+1][ld[i][dl][DN][RT]]-v[i+1][ld[i][dl][DN][LF]-1]);
                        continue;
                    }
                }
                if(ld[i-1][ul][DN][LF]>=ld[i][dr][UP][RT]) continue;
                if(ld[i-1][ur][DN][RT]<=ld[i][dl][UP][LF]) continue;
                int usum=v[i][ld[i-1][ur][DN][RT]]-v[i][ld[i-1][ul][DN][LF]-1];
                int dsum=v[i+1][ld[i][dr][DN][RT]]-v[i+1][ld[i][dl][DN][LF]-1];
                int LR=max(v[i][ld[i-1][ul][DN][RT]],v[i][ld[i][dl][UP][RT]]);
                int LL=min(v[i][ld[i-1][ul][DN][LF]-1],v[i][ld[i][dl][UP][LF]-1]);
                int RR=max(v[i][ld[i-1][ur][DN][RT]],v[i][ld[i][dr][UP][RT]]);
                int RL=min(v[i][ld[i-1][ur][DN][LF]-1],v[i][ld[i][dr][UP][LF]-1]);
                int msum;
                if(LR>=RL) msum=RR-LL;
                else msum=LR-LL+RR-RL;
                maxz(dp[i][dl][dr],dp[i-1][ul][ur]-usum+msum+dsum);
                if(debug) {
                    printf("-%d %d %d %d %d +%d\n",usum,LL,LR,RL,RR,dsum);
                    printf("  dp[%d][%d][%d]=%d\n",i-1,ul,ur,dp[i-1][ul][ur]);
                    printf("->dp[%d][%d][%d]=%d\n",i,dl,dr,dp[i][dl][dr]);
                }
                maxz(ans,dp[i][dl][dr]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}
}}}

#include<bits/stdc++.h>
#define eb emplace_back
#define fir first
#define sec second
#define all(v) v.begin(),v.end()
#ifdef LOCAL
    #define debug 0
#else
    #define debug 0
#endif
using namespace std;
typedef long long ll;
const int N=1005,M=5005,L=12,INF=1<<30;
const int LF=0,RT=1,UP=0,DN=1;
int ld[N][L][2][2],ld0[N][L],ln[N],v[N][M];
int dp[N][L][L];
int n,m;
char ss[N][M],t[M];
inline void maxz(int& a,int b) { if(a<b) a=b; }
int main()
{
    int i,j,ans=0;
    scanf("%d%d",&n,&m);
    ans=0;
    for(i=0;i<n;i++) {
        auto s=ss[i];
        scanf("%s",s+2);
        scanf("%s",t+2);
        s[1]=s[m+2]='0';
        if(i) {
            for(j=0;j<ln[i-1];j++) {
                while(s[ld[i-1][j][DN][LF]]=='-') ld[i-1][j][DN][LF]--;
                while(s[ld[i-1][j][DN][RT]]=='-') ld[i-1][j][DN][RT]++;
            }
        }
        v[i][0]=0;
        for(j=1;j<=m+2;j++) v[i][j]=v[i][j-1]+(isdigit(s[j])?s[j]-'0':0);
        for(j=1;j<=m+2;j++) {
            if(t[j]=='|') {
                int l=ln[i]++;
                ld[i][l][UP][LF]=ld[i][l][UP][RT]=ld[i][l][DN][LF]=ld[i][l][DN][RT]=ld0[i][l]=j;
            }
        }
        for(j=0;j<ln[i];j++) {
            while(s[ld[i][j][UP][LF]]=='-') ld[i][j][UP][LF]--;
            while(s[ld[i][j][UP][RT]]=='-') ld[i][j][UP][RT]++;
        }
    }
    memset(dp,-1,sizeof(dp));
    for(i=0;i<ln[0];i++) for(j=i;j<ln[0];j++) {
        if(i==j&&ld[0][i][DN][LF]==ld[0][i][DN][RT]) maxz(ans,v[1][ld[0][j][DN][RT]]-v[1][ld[0][i][DN][LF]-1]);
        else {
            dp[0][i][j]=v[1][ld[0][j][DN][RT]]-v[1][ld[0][i][DN][LF]-1];
            maxz(ans,dp[0][i][j]);
            if(debug) printf("dp[0][%d][%d]=%d\n",i,j,dp[0][i][j]);
        }
    }
    for(i=0;i<ln[n-1];i++) ld[n-1][i][DN][LF]=1,ld[n-1][i][DN][RT]=m;
    memset(v[n],0,sizeof(v[n]));
    if(debug) {
        for(i=0;i<n;i++) {
            for(j=0;j<ln[i];j++) printf("(%d,%d|%d,%d)",ld[i][j][UP][LF],ld[i][j][UP][RT],ld[i][j][DN][LF],ld[i][j][DN][RT]);
            puts("");
        }
        for(i=0;i<=n;i++) {
            for(j=0;j<=m+2;j++) printf("%02d ",v[i][j]);
            puts("");
        }
    }
    int ul,ur,dl,dr;
    for(i=1;i<n;i++) {
        for(ul=0;ul<ln[i-1];++ul) for(ur=ul;ur<ln[i-1];++ur) {
            if(dp[i-1][ul][ur]<0) continue;
            for(dl=0;dl<ln[i];++dl) for(dr=dl;dr<ln[i];++dr) {
                if(dl==dr) {
                    if(ld[i][dl][UP][LF]==ld[i][dl][UP][RT]) continue;
                    if(ld[i][dl][DN][LF]==ld[i][dl][DN][RT]) {
                        maxz(ans,dp[i-1][ul][ur]+v[i+1][ld[i][dl][DN][RT]]-v[i+1][ld[i][dl][DN][LF]-1]);
                        continue;
                    }
                }
                if(ld[i-1][ul][DN][LF]>=ld[i][dr][UP][RT]) continue;
                if(ld[i-1][ur][DN][RT]<=ld[i][dl][UP][LF]) continue;
                int usum=v[i][ld[i-1][ur][DN][RT]]-v[i][ld[i-1][ul][DN][LF]-1];
                int dsum=v[i+1][ld[i][dr][DN][RT]]-v[i+1][ld[i][dl][DN][LF]-1];
                int LR=max(v[i][ld[i-1][ul][DN][RT]],v[i][ld[i][dl][UP][RT]]);
                int LL=min(v[i][ld[i-1][ul][DN][LF]-1],v[i][ld[i][dl][UP][LF]-1]);
                int RR=max(v[i][ld[i-1][ur][DN][RT]],v[i][ld[i][dr][UP][RT]]);
                int RL=min(v[i][ld[i-1][ur][DN][LF]-1],v[i][ld[i][dr][UP][LF]-1]);
                int msum;
                if(LR>=RL) msum=RR-LL;
                else msum=LR-LL+RR-RL;
                maxz(dp[i][dl][dr],dp[i-1][ul][ur]-usum+msum+dsum);
                if(debug) {
                    printf("-%d %d %d %d %d +%d\n",usum,LL,LR,RL,RR,dsum);
                    printf("  dp[%d][%d][%d]=%d\n",i-1,ul,ur,dp[i-1][ul][ur]);
                    printf("->dp[%d][%d][%d]=%d\n",i,dl,dr,dp[i][dl][dr]);
                }
                maxz(ans,dp[i][dl][dr]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}