ch_5103 传纸条

dp维度优化

优化 ：y=i-x

#include<iostream>
#include<cstdio>

#define ri register int
#define u int

namespace opt {

    inline u in() {
        u x(0),f(1);
        char s(getchar());
        while(s<'0'||s>'9') {
            if(s=='-') f=-1;
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x*f;
    }

}

using opt::in;

#define NN 105

#include<algorithm>

namespace mainstay {

    u N,M,a[NN][NN],f[NN<<1][NN][NN];

    inline void solve() {
        std::cin>>N>>M;
        for(ri i(1); i<=N; ++i) {
            for(ri j(1); j<=M; ++j) {
                std::cin>>a[i][j];
            }
        }
        for(ri i(2); i<=N+M; ++i) {
            for(ri x1(1); x1<i; ++x1) {
                for(ri x2(1); x2<i; ++x2) {
                    f[i][x1][x2]=std::max(f[i][x1][x2],f[i-1][x1][x2]);
                    f[i][x1][x2]=std::max(f[i][x1][x2],f[i-1][x1][x2-1]);
                    f[i][x1][x2]=std::max(f[i][x1][x2],f[i-1][x1-1][x2]);
                    f[i][x1][x2]=std::max(f[i][x1][x2],f[i-1][x1-1][x2-1]);
                    f[i][x1][x2]+=a[x1][i-x1]+a[x2][i-x2];
                    if(x1==x2) f[i][x1][x2]-=a[x1][i-x1];
                }
            }
        }
        std::cout<<f[N+M][N][N];
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    std::ios::sync_with_stdio(false);
    mainstay::solve();

}