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 ?

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.

For each case, you just output the MAX qualities you can eat and then get.

2009 Multi-University Training Contest 4 - Host by HDU

gaojie   |   We have carefully selected several similar problems for you:   2830  2577  2870  1159  1176 

#include <stdio.h>
#include <iostream>
using namespace std;
#define M 200001
int vis[M],map[M],dp[M],f[M];
int max(int a[],int n)                //求在a[]中最大不连续子序列和。  
{
  int i;
  f[0]=map[0]=0;
  f[1]=map[1]=a[1];
  for(i=2;i<=n;i++)                   //要保证i-2不会数组越界。
  {
      f[i]=map[i-2]+a[i];                  //由于要隔一个取。所以取了a[i],就不能取a[i-1],所以最大值就是前i-2个数的最大值+a[i].
      map[i]=f[i]>map[i-1]?f[i]:map[i-1];  //假设取a[i]要更大，更新map[i]的值。  
  }
 return map[n];
}
int main(int i,int j,int k)
{  
    int n,m,tot,cur;
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                scanf("%d",&vis[j]);
            dp[i]=max(vis,m);
        }
    printf("%d\n",max(dp,n));
    }
    return 0;
}