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.

  
  

   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
  
  

  
  

   242
  
  

2009 Multi-University Training Contest 4 - Host by HDU

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

  
  

   这道题意思能够转换成：
  
  

  
  

   对每一行，不能有间隔的取一个子序列，即取该行的最大不连续子序列和；
  
  

  
  

   再从上面全部值中，取其最大不连续子序列和；就相当于隔一行取了
  
  

  
  


  
  

  
  

   状态：f[i]表示取第i个元素(a[i]必取)的最大值，map[i]表示取到a[i]（可不取）时的最大值
  
  

  
  

   状态转移：f[i]=map[i-2]+a[i];map[i]=max{map[i-1],f[i]};


  
  

#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;
}