首页 > 其他 > 详细

HDU2490 parade

时间:2015-06-18 15:02:27      阅读:125      评论:0      收藏:0      [点我收藏+]

题目大意:一个n+1行m+1列的表格,每个格子两个数w和c,表示经过该格子的happy和体力消耗值tireness。现在从最下面任意处开始,可以向左向右向上走。但不能向下。每个格子不能经过两次。在每一行消耗的体力不能超过k。问能得到最多的happy值是多少。

n<=100,m<=10000,k<=3000000

分析:明显是一个dp问题。设f[i][j]表示在当前走到第i行第j个格子是能够得到的最大的happy值。f[i][j]=max(f[i-1][p]+sumh(p,j))  (sumt(p,j)<=k) 

sumh(p,j)表示p到j的happy值之和,sumt表示p到j的消耗体力值之和。

对每一行的happy消耗值求前缀和,用一个递增的单调队列保存sumh。对于该行的第j个格子,则可以在O(1)的时间内找到左边sumh最小的格子p,从而使得sumh[j]-sumh[p]最大,即从格子p+1到格子j的happy值之和最大。

格子j的右边可以类似的处理。

于是总的事件复杂度为O(n,m)。

 

HDU2490 parade

原文:http://www.cnblogs.com/hefenghhhh/p/4585618.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!