`
king_tt
  • 浏览: 2084526 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

uva-1427 Parade (单调队列优化dp)

 
阅读更多


本文出自 http://blog.csdn.net/shuangde800



题目链接uva-1427 hdu-2490 poj-3923

题意

F城由n+1个横向路和m+1个竖向路组成。你的任务是从最南边的路走到最北边的路,使得走过的路上的高兴值和最大(注意,一段路上的高兴值可以是负数)。同一段路不能经过两次,且不能从北往南走。另外,在每条横向路上所花的时间不能超过k


思路

这题在uva和LA上又是不能评测, 于是在hdu和poj上评测了这题

这题状态比较容易想到, f(i, j)表示走到第i行第j点的最大价值
对于每一点,可以从下一行的走上来,也可以从左边走过来,也可以从右边走过来
设L(i, j)表示第i行从左边走到j点的最大价值,R(i, j)表示第i行从右边走过来的最大价值
可以得到, f(i, j) = max{ L(i,j), R(i, j), f(i+1, j) }
关键是要求L(i, j)和R(i, j)

sum(i, j)表示第i行的前j个路段价值之和
L(i, j) = max{ f(i+1, k) + sum(i, j) - sum(i, k) | 1<=k<=j && k走到j的总时间 <= k}
转换可以变成:
L(i, j) = max{ f(i+1, k) - sum(i, k)| 1<=k<=j && k走到j的总时间 <= k} + sum(i, j)

所以只要维护一个k,使得
f(i+1, k) - sum(i, k)的值最大,这可以用单调队列来维护这个值

求R(i, j)的方法也可L一样



代码

<script src="https://code.csdn.net/snippets/616.js" type="text/javascript"></script>

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics