hdu 2845 beans

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
Output
242

 
 
题意：给定一个矩阵，每一行中不能选择相邻的数字，不能选择相邻的行，求出所选数的和的最大值。

思路：先对每一行求出其最大不连续和。对每一行所求出的最大值，再求一次最大不连续和。

状态转移方程为
dp[i+1] = max (dp[i], dp[i-1]+num)　　//表示第 i 个位置所能达到的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 200005;
int dp[MAX_N], row[MAX_N];
int N,M,num;
int  ()
{
    while(~scanf("%d%d",&M,&N)) {
        dp[0] = dp[1] = 0;
        for (int j=1; j<=M; ++j) {
            for (int i=1; i<=N; ++i) {
                scanf("%d",&num);
                dp[i+1] = max (dp[i], dp[i-1]+num);
            }
            row[j] = dp[N+1];
        }
        for (int i=1; i<=M; ++i)
            dp[i+1] = max (dp[i], dp[i-1]+row[i]);
        printf("%dn",dp[M+1]);
    }
    return 0;
}