ean-eating is an interesting game, everyone owns an M*N matrix, which is filled with different qualities beans. Meantime, there is only one bean in any 1*1 grid. Now you want to eat the beans and collect the qualities, but everyone must obey by the following rules: if you eat the bean at the coordinate(x, y), you can’t eat the beans anyway at the coordinates listed (if exiting): (x, y-1), (x, y+1), and the both rows whose abscissas are x-1 and x+1. 

Now, how much qualities can you eat and then get ?
InputThere are a few cases. In each case, there are two integer M (row number) and N (column number). The next M lines each contain N integers, representing the qualities of the beans. We can make sure that the quality of bean isn't beyond 1000, and 1<=M*N<=200000.OutputFor each case, you just output the MAX qualities you can eat and then get.
题意：取一个数字，那么相邻的两行的所有数字和同一行的相邻两列的数字就不能再取了，求最大总和。

1.首先单独对每行的数据进行dp处理，得到一个最大值；

2,.每行的最大值又组成一个新的数组，再次dp求最大值

下面贴代码：
 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define INF 0x3fffffff
#define maxn 200005
#define mod 998244353
int n,m,k,t;
int a[maxn],dp[maxn];
int main(){
    while(~scanf("%d%d",&n,&m)){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            scanf("%d",&a[j]);
        for(int j=2;j<=m;j++)
            a[j]=max(a[j-2]+a[j],a[j--1]);
        dp[i]=a[m];
    }    
    for(int i=2;i<=n;i++)
        dp[i]=max(dp[i-2]+dp[i],dp[i-1]);
    printf("%d\n",dp[n]);
    }
}