Beans HDU - 2845 (dp)

题目链接:点我

题目

Bean-eating is an interesting game, everyone owns an MN matrix, which is filled with different qualities beans. Meantime, there is only one bean in any 11 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

题意:

一个 n * m的矩阵,矩阵的每个点有不同的值,你每次可以选取坐标为(x, y) 的矩阵但是选取了这个点后你不能选取它左右相邻的点,也不能选取上一行和下一行,问最大值是多少.

思路:

动态规划, 对于一行来说，相邻的数不可同时取，容易得到状态转移方程：
dp[i]=max(dp[i-2]+a[i],dp[i-1]); 每一行和每一列进行相同的处理.

代码:

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;

const int maxn = 200000+10;
int dpx[maxn],dpy[maxn];

int main(){
    int n,m;
    while(scanf("%d %d", &n, &m) != EOF){
        for(int i = 2;i<=n+1;++i){
            for(int  j = 2;j<=m+1;++j){
                int s;
                scanf("%d", &s);
            dpy[j]=max(dpy[j-1],dpy[j-2]+s);
            }
            dpx[i]=max(dpx[i-1],dpx[i-2]+dpy[m+1]);
        }
        printf("%d\n",dpx[n+1]);
    }
    return 0;
}