首页 > 代码库 > hdu 2845 Beans（DP）
hdu 2845 Beans（DP）
题意：
M*N的矩阵，每个格子上有一个值。
规则：如果你拾起了某个格子（i,j）上的值，那么第i-1行、第i+1行、(i,j-1)格子上、(i,j+1)格子上的值都不能取。
问最多可以取得多少值（最大值）。
思路：
如果某行取了某一个值，则它的前一行和后一行都不能取。所以我们必须知道这行可以取得的最大值是多少。
dp[i]=max( dp[i-1],dp[i-2]+a[i] ) dp[i]：前i个数能获得的最大值。第i个可以取，可以不取。
当每行的dp[N]都算出来后，可以发现从行的角度看，dp方程也是一样的！
看代码
代码：
int a[200005], b[200005];int dp1[200005], dp[200005];int m,n;int main(){ while(scanf("%d%d",&m,&n)!=EOF){ mem(dp1,-inf); mem(dp,-inf); mem(b,-inf); rep(i,1,m){ rep(j,1,n){ scanf("%d",&a[j]); } dp1[1]=a[1]; dp1[2]=max(a[1],a[2]); rep(j,3,n) dp1[j]=max( dp1[j-2]+a[j],dp1[j-1] ); rep(j,1,n) b[i]=max( b[i],dp1[j] ); } dp[1]=b[1]; dp[2]=max(b[1],b[2]); rep(i,3,m) dp[i]=max( dp[i-2]+b[i],dp[i-1] ); int ans=-inf; rep(i,1,m) ans=max( ans,dp[i] ); printf("%d\n",ans); } return 0;}
hdu 2845 Beans（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。