首页 > 代码库 > hdu2845(dp)
hdu2845(dp)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2845
题意:给你一个n*m的矩阵,每个位置有一定数量的豆子,如果你去map[x][y]位置上的豆子,则map[i-1][]行和map[i+1][]行,以及map[i][j-1]和map[i][j+1]位置上的豆子都不能再取。
分析:水dp,先算出每行的最大值,在对n行的最大值dp得结果。dp[i][1]表示前i个且取了第i个达到的最大值,dp[i][0]表示前i个且不取第i个达到的最大值。
状态转移方程:dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i-1][0]+b[i];
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 200010using namespace std;int a[N];int mx[N],dp[N][2];int n,m;int solve(int b[],int sum){ for(int i=1; i<=sum; i++) { dp[i][1]=dp[i-1][0]+b[i]; dp[i][0]=max(dp[i-1][0],dp[i-1][1]); } return max(dp[sum][0],dp[sum][1]);}int main(){ while(scanf("%d%d",&n,&m)>0) { for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { scanf("%d",&a[j]); } mx[i]=solve(a,m); } int ans=solve(mx,n); printf("%d\n",ans); }}
hdu2845(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。