Bean-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 ?
Input
There 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.
Output
For each case, you just output the MAX qualities you can eat and then get.
Sample Input
4 6
11 0 7 5 13 9
78 4 81 6 22 4
1 40 9 34 16 10
11 22 0 33 39 6
Sample Output
242
题解：
比赛的时候没想出来，看了博客懂了，由题意就是求两次不连续最大子序列和，横着一次竖着一次，讲解看注释
我看的博客：http://www.2cto.com/kf/201408/323478.html
代码：
#include<iostream>
#include<stdio.h>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
#include<deque>
#include<stack>
using namespace std;
int a[20005];//数据保存
int p1[20005];//i处取
int p2[20005];//i处不取
int b[20005];//每一行的情况
int m,n;
int dp(int c[],int len)//求不连续最大子序列和
{
int i,j;
p1[0]=0;//初始化一下
p2[0]=0;
for(i=1;i<=len;i++)
{
p1[i]=p2[i-1]+c[i];//取的时候即为不取的时候+当前值
p2[i]=max(p1[i-1],p2[i-1]);//不取即前一个取的情况和不取的情况的最大值
}
return max(p1[len],p2[len]);//len处取与不取的最大值
}
int main()
{
int i,j,x;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&a[j]);
}
b[i]=dp(a,m);//存下每一行最大不连续子序列和
}
printf("%d\n",dp(b,n));//输出每一列最大不连续子序列和
}
return 0;
}
