HDU 2845 DP Beans

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2845

分析：题目意思就是不能有任何两个数在相邻的行和相邻的列中，先对某一行分析，如果先取了第1个数，则接下来可以取第3或4个数(因为求所有取的数之和最大，所以不可能一下跳过3个以上)，如果先取第2个数，接下来可以取第4或5个数，依此类推．．．．．．

从这里可以观察到，当取到第4个数时，所有取出数的和的大小取决于第1个数和第2个数的大小，意思就是当取到第i个数时，和的大小取决于取到第i-3个数和取到第i-2时和的大小，即c[i]=c[i]+max(c[i-2],c[i-3])；那么对于每一列也同样考虑，可以得到r[i]=r[i]+max(r[i-2],r[i-3])．

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int r[2000001], c[2000001];
int main(){
    int n,m;
    while (~scanf("%d%d",&n,&m)) {
        r[0]=0;c[0]=0;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++)
                scanf("%d",&c[j]);
            for(int j=3;j<=m; j++)
                c[j]+=max(c[j-2],c[j-3]);
            r[i]=max(c[m-1],c[m]);
            if(i>=3)r[i]+=max(r[i-2],r[i-3]);
        }
        printf("%d\n", max(r[n],r[n-1]));
    }
    return 0;
}