[poj 2948]Martian Mining

题目链接

http://poj.org/problem?id=2948

大意

在 \(m \times n\) 的矿区中，储存着两种矿石（B种 和 Y种），其中B种矿石只能向北运输，Y种矿石只能向西运输，现在要铺设传送带（不能拐弯），求出能运送矿石的最大值。

题解

先用前缀和的技巧把南北向和东西向的矿石数量算出来。然后就是简单的线性DP了。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int f[505][505],b[505][505],y[505][505];
int main()
{
 int n,m;
 while(~scanf("%d%d",&n,&m)&&n&&m)
 {
  memset(f,0,sizeof(f));
  memset(y,0,sizeof(y));
  memset(b,0,sizeof(b));
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
   {
    scanf("%d",&y[i][j]);
    y[i][j]+=y[i][j-1];
   }
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
   {
    scanf("%d",&b[i][j]);
    b[i][j]+=b[i-1][j];
   }
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
    f[i][j]=max(f[i-1][j]+y[i][j],f[i][j-1]+b[i][j]);
  printf("%d\n",f[n][m]);
 }
 return 0;
}