LA 3530 Martian Mining DP .

题目地址：Martian Mining

题目的意思就是，每个格子可以放 朝上的管子或者朝左的管子，问最多能得到多少矿

d[i][j][k]表示到i，j格子且此格子是k放置的， 最多能得到多少矿

后来写出来后发现不行，状态转移不行，你知道 此格子怎么放，周围的格子怎么放，但是要判断矿能不能送到目的地还需要，将沿途的所有k==1的格子加上

所以换个状态定义，d[i][j][k]表示i，j这一个格子，若k==1，那么 Grid[i][1~j] 水管都是竖着放的 ，那么状态也好转移了

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=500+5;
int A[maxn][maxn],B[maxn][maxn],d[maxn][maxn][2];
int main(int argc, char const *argv[])
{
 int n,m;
 while(scanf("%d%d",&n,&m)==2&&n+m){
    
 REP(i,1,n) REP(j,1,m) scanf("%d",&A[i][j]),A[i][j]+=A[i][j-1];
 REP(i,1,n) REP(j,1,m) scanf("%d",&B[i][j]),B[i][j]+=B[i-1][j]; memset(d,0,sizeof(d));
 REP(i,1,n) REP(j,1,m) {
    
 d[i][j][1]=B[i][j]+max(d[i][j-1][1],d[i][j-1][0]);
 d[i][j][0]=A[i][j]+max(d[i-1][j][0],d[i-1][j][1]);
 }
 printf("%d\n", max(d[n][m][0],d[n][m][1]));
 }
 return 0;
}