题解 P2380 【狗哥采矿】

YoungLove · 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(){;}

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