HDU 2845 Beans

水深无声 2022-04-16 06:23 86阅读 0赞

## 原题目链接：[HDU2845][] ##

--------------------

## 分类 ##

HDU 动态规划 贪心

--------------------

## 题意 ##

![convip1-1001-1.JPG][]  
在图中取数，例如取了81之后，同一行的相邻两个不能取，还有81的上面那行和下面那行也不能取，问能取到的最大和是多少

--------------------

## 想法 ##

\*\*dp的经典题目就是说这种选数的题，慢慢发现，dp的原则：处理子问题，根据子问题的最优解慢慢求得总的最优解，这个题目就是，先求我选一行中数的最大和，再求前i行的最大和，一直到n+1行得出来的不就是整个矩阵的最优解了 ----> dp思路 \*\*  
先求某一行能获得的最大值,然后求所有行能获得的最大值.

--------------------

## 代码 ##

312ms

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/18 */
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 222222;
    int dpx[maxn],dpy[maxn];//dpx[i]用来存当前这一行取前i个数的最大值,dpy[i]用来存前i行可得最大值 
    int n ,m, tem;
    
    /** dp的经典题目就是说这种选数的题，慢慢发现，dp的原则：处理子问题，根据子问题的最优解慢慢 求得总的最优解，这个题目就是，先求我选一行中数的最大和，再求前i行的最大和，一直到n+1行 得出来的不就是整个矩阵的最优解了 ----> dp思路 */
    
    int main()
    { 
    	while(cin >> n >> m)
    	{ 
    		memset(dpx, 0, sizeof(dpx));
    		memset(dpy, 0, sizeof(dpy));
    		for(int i=2;i<=n+1;i++)
    		{ 
    			for(int j=2;j <= m+1;j++)
    			{ 
    				scanf("%d",&tem);
    				dpx[j] = max(dpx[j-1], tem + dpx[j-2]);//当前这行前j列能获得的最大值.
    			}
    			dpy[i] = max(dpy[i-1], dpy[i-2] + dpx[m + 1]);//前i行最大能获得的最大值.
    		}
    		printf("%d\n",dpy[n + 1]);
    	}
    }

--------------------

[HDU2845]: http://acm.hdu.edu.cn/showproblem.php?pid=1069
[convip1-1001-1.JPG]: /images/20220416/33451721e8ff4df987d31272accd0176.png