学步园

小记：之前因为N*M<= 20W，所以我是使用malloc动态开辟的，可能是转移方程的问题，然后一直WA，后来换了个转移方程就 1A了

思路：对于每一行计算这一行所能得到的最大值，

对于每一行的最大值的计算，

dp[j][1] 表示前1-j个值包括第j个值的最大值

dp[j][0]表示前1-j个值不包括第j个值的最大值

那么每一行的最大值就是 max(dp[m-1][1], dp[m-1][0])

对于前1-i行， 

ans[i][0] 表示不包括第i行所能得到的最大值

ans[i][1] 表示包括第i行所能得到的最大值

那么结果就是max(ans[n-1][1], ans[n-1][0])

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define REP(a,b,c) for(int a = b; a < c; ++a)
#define eps 10e-8

const int MAX_ = 200010;
const int N = 3000010;
const int INF = 0x7fffffff;

//int p[MAX_][MAX_];
int dp[MAX_][2];
int ans[MAX_][2];

int main() {
    int n, T, m, k;
    //char c, str[10];
    //scanf("%d", &T);
    while(~scanf("%d%d", &n, &m)) {
        /*int ***dp = (int***)malloc(n * sizeof(int));
        REP(i, 0, n){
            *(dp+i) = (int **)malloc(m * sizeof(int));
            REP(j, 0, m){
                *((*(dp+i)) + j) = (int *)malloc(2 * sizeof(int));
            }
        }*/

        REP(i, 0, n) {
            REP(j, 0, m) {
                scanf("%d", &k);
                dp[j][1] = k;

                if(j > 1)
                dp[j][1] += max(dp[j-2][1], dp[j-2][0]);

                if(j > 0)
                dp[j][0] = max(dp[j-1][0], dp[j-1][1]);
                else dp[j][0] = 0;

            }
            int tmp = max(dp[m-1][0], dp[m-1][1]);

            //printf("%d\n", tmp);
            ans[i][1] = tmp;

            if(i > 1){
                ans[i][1] += max(ans[i-2][1], ans[i-2][0]);
            }

            if(i > 0){
                ans[i][0] = max(ans[i-1][1], ans[i-2][0]);
            }
            else ans[i][0] = 0;

        }
        int re = max(ans[n-1][1], ans[n-1][0]);

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

        //free(p);
        //free(dp);
    }
    return 0;
}