自动搬运

查看原文

来自洛谷，原作者为

	YoungLove **

搬运于2025-08-24 21:37:03，当前版本为作者最后更新于2017-09-27 14:36:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Youngsc

我们定义$f[i][j]$为在以$(i,j)$为右下角的子矩阵中的最大采矿量，由题意我们可知，如果$(i,j)$是向左转移矿，那么$(i,j-1)$,一定也是向左，$(i,j-2)$一直到$(i,1)$都是向左，同理如果$(i,j)$是向上转移矿，那么$(i-1,j)$,一定也是向上，$(i-2,j)$一直到$(1,j)$都是向左。这就可以其实我们用前缀和去维护一段区间的采矿量。

在转移时，我们只关心当前$(i,j)$的采矿方向。设$A[i][j]$为向上的前缀和，$B[i][j]$为向左的前缀和，那么转移方程$f[i][j]=max(f[i-1][j]+B[i][j],f[[i][j-1]+A[i][j])$.

俄日额貌似是多组数据，我也不是太清楚反正第一次就那么些然后一遍过了。。。

代码在这里

# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <vector>
# include <queue>
# include <cmath>
# define R register

using namespace std;

int n,m,a[510][510],b[510][510],f[510][510];

template <typename T> void in(R T &a){
    R char c = getchar();R T x=0,f=1;
    while(!isdigit(c)) {if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c = getchar();
    a=x*f;
}

inline void maxx(R int &a,const int b){a>b? 0:a=b;}
inline void minn(R int &a,const int b){a<b? 0:a=b;}

inline int youngsc(){
    while(1){
        in(n),in(m);
        if(m+n==0)break;

        for(R int i=1; i<=n; ++i)
            for(R int j=1; j<=m; ++j)
                in(a[i][j]),a[i][j] += a[i][j-1];

        for(R int i=1; i<=n; ++i)
            for(R int j=1; j<=m; ++j)
                in(b[i][j]),b[i][j] += b[i-1][j];

        for(R int i=1; i<=n; ++i)
            for(R int j=1; j<=m; ++j)
                f[i][j] = max(f[i-1][j]+a[i][j],f[i][j-1]+b[i][j]);

        printf("%d\n",f[n][m]);
    }
    return 0;
}
int yg = youngsc();
int main(){;}

（减少代码复制，共创美好洛谷）