本文主要是介绍hdu 2845 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu 2845 题解
题目大意：同一行里必须隔一个及以上个数来取数，行与行之间也是隔一行及以上。
题目解析：想要求得一行里能取到的最大和值可以通过动态转移方程
dp[i] = max(dp[i-1], dp[i-2] + a[i] ); 得到每行的最大值之后，就是开始求最后的结果，此时把得到的最大值数组再通过如上的转移方程得到最终结果。
二维动态用两次一维动态完成。能这么做的关键是行内数字间的关系和行间的关系达到高度的一致性。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int a[200005];
int b[200005];
int dp[200005];
int getDP(int b[], int len){
inti, j;
dp[0]= b[0];
dp[1]= b[1];
for(i = 1; i < len; i ++ ){
dp[i]= max( dp[i-1], dp[i-2]+b[i]);
}
returndp[len-1];
}
int main()
{
intm, n, i, j;
while(cin >> m >> n )
{
for( i = 0; i < m; i ++ ){
for( j = 0; j < n; j ++ ) {
cin>> b[j];
}
a[i]= getDP(b, n);
}
cout<<getDP(a,m)<<endl;
}
return0;
}
这篇关于hdu 2845 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
