Beans

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2518    Accepted Submission(s): 1250

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

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

　　 题目的意思是给一个矩阵，没一点放置一定数量的豆，求出最多能吃多少个豆。但是吃豆有一定的规则，如果吃点（x，y）的豆，那么点（x，y-1）、点（x，y+1）和点（x，y）所在行的上一行和下一行的豆都不能吃。所以我们要做的事首先将每一行所能吃到的最大豆的数量求出来，即求出每一行非连续的最大子序列和，然后将每一行所求的最大豆数量保存到数组序列中，同样的方法求出数组序列的非连续的最大子序列和即为所能吃到的最大豆的数量。

　　状态转移方程：sum[i] = dp[i-2]+a[i]，dp[i] = max(sum[i],dp[i-1])，2<=i<=n，初始化sum[0]=dp[0]=0,sum[1]=dp[1]=a[1]。

我的代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define N 200003
 5 int sum[N],dp[N],map[N],row[N];
 6 
 7 int solve(int a[],int n)
 8 {
 9     int i;
10     sum[0] = 0;
11     dp[0] = 0;
12     sum[1] = a[1];
13     dp[1] = a[1];//数组dp代表最大豆的数量
14     for(i=2; i<=n; i++)
15     {
16         sum[i] = dp[i-2]+a[i];
17         dp[i] = max(sum[i],dp[i-1]);
18     }
19     return dp[n];
20 }
21 
22 int main()
23 {
24     int i,j,n,m,sum;
25     while(scanf("%d%d",&n,&m)!=EOF)
26     {
27         for(i=1; i<=n; i++)
28         {
29             for(j=1; j<=m; j++)
30                 scanf("%d",&map[j]);
31             row[i] = solve(map,m);
32         }
33         sum = solve(row,n);
34         printf("%d\n",sum);
35     }
36     return 0;
37 }

View Code