洛谷 P2380 狗哥采矿

题目背景

又是一节平静的语文课

狗哥闲来无事，出来了这么一道题

题目描述

一个n*m的矩阵中，每个格子内有两种矿yeyenum和bloggium，并且知道它们在每个格子内的数量是多少。最北边有bloggium的收集站，最西边有 yeyenum 的收集站。现在要你在这些格子上面安装向北或者向西的传送带(每个格子只能装一种)。问最多能采到多少矿？

输入输出格式

输入格式：

第一行包含两个整数n,m,( 1 ≤ n ≤ 500, 1 ≤ m ≤ 500)。接下来n行m列，表示每个格子中可以传送到yeyenum的数量(小于1000)，再接下来n行m列，表示每个格子中可以传送到bloggium的数量。n, m 同时为0结束。

输出格式：

每组测试数据仅输出一个数，表示最多能采到的矿。

输入输出样例

输入样例#1：

4 4

0 0 10 9

1 3 10 0

4 2 1 3

1 1 20 0

10 0 0 0

1 1 1 30

0 0 5 5

5 10 10 10

0 0

输出样例#1：

98

说明

传输过程中不能转弯，只能走直路。

前缀和+棋盘dp

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

#define N 600

int n,m,ans,f[N][N],a[N][N],b[N][N];

inline int max(int a,int b){return a>b?a:b;}

int main()

{

    for(;scanf("%d%d",&n,&m)&&n&&m;)

    {

        memset(f,,sizeof(f));

        ans=;

        for(int i=;i<=n;++i)

         for(int x,j=;j<=m;++j)

          scanf("%d",&x),a[i][j]=a[i][j-]+x;

        for(int i=;i<=n;++i)

         for(int x,j=;j<=m;++j)

          scanf("%d",&x),b[i][j]=b[i-][j]+x;

        for(int i=;i<=n;++i)

         for(int j=;j<=m;++j)

          f[i][j]=max(f[i-][j]+a[i][j],f[i][j-]+b[i][j]),ans=max(ans,f[i][j]);

        printf("%d\n",ans);

    }

    return ;

}