Beans

Problem Description

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

 

Sample Output

 

填了一个格子以后他的左右相邻的格子和上下两行的格子就不能再选，我们不妨先从一行入手，假设每一行的最大价值已经得出，我们要做的只是从这些行中挑选出几个使其满足题意且价值最大，

（显然我们可以把每一行的最大价值抽象为一个格子，这样所有的行排成一列抽象为一行！只要再计算一次这“一行”的最大价值就好了！挑选一行之后上下不可挑与挑选一个格子后左右不可再跳显然类似！属于同一个问题）

只考虑左右的情况，根据贪心的原理，显然每一行挑选出的格子与格子的间隔k满足(1<=k<=2),想不通的话手画！

所以我们要计算的问题出现了，就是最大不连续子段和，因为彼此不连续所以间隔至少为1，为何至大为2：（如果超出2的话这两个元素之间还是有元素可以选择，由于全为正数所以不可放过！）

我们用dp[i]表示从i到最后一个元素的最大不连续子段和，则dp[i]=max(a[i]+dp[i+2],dp[i+1])|{dp[n]=a[n],dp[n-1]=max(a[n],a[n-1])}

也可以写成正序：dp[i]=max(a[i]+dp[i-2],dp[i-1])|{dp[1]=a[i]}

#include<bits/stdc++.h>
using namespace std;
int dp[200005];
int h[200005];
int book[200005];
int n,m;
int init(int a[],int len)
{
dp[len]=a[len];
dp[len-1]=max(a[len],a[len-1]);
for(int i=len-2;i>=1;--i){
dp[i]=max(a[i]+dp[i+2],dp[i+1]);
}
return dp[1];
}
int main()
{
int i,j,k;
while(cin>>n>>m){int s1=0,s2=0;
for(i=1;i<=n;++i){
for(j=1;j<=m;++j)
scanf("%d",&h[j]);
book[i]=init(h,m);
}
printf("%d\n",init(book,n));
}
return 0;
}