本文出自 http://blog.csdn.net/shuangde800
题意
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>
分享到:
相关推荐
parade-A data processing engine and service. 一个数据处理引擎和服务
灯塔游行一个Node.js命令行工具,可对域进行爬网并使用每个页面的灯塔性能数据来编译报告。为什么?有很多很棒的工具可以在单个网页上进行性能分析。我们都在使用和 。但是,如果您要评估整个站点的性能特征该怎么办...
泰克公司宣布Parade科技公司(Parade Technologies Inc.)成功使用泰克测试设备验证了其新型DP501 DisplayPort发送器对新兴DisplayPort标准的一致性要求。 DisplayPort作为视频电子标准协会(VESA)制订的一项新的...
python库。 资源全名:parade-0.1.14-py3-none-any.whl
python库,解压后可用。 资源全名:parade-0.1.10-py3-none-any.whl
资源来自pypi官网。 资源全名:parade-0.1.10-py3-none-any.whl
资源来自pypi官网。 资源全名:parade-0.1.20.6-py3-none-any.whl
Keypress Parade是一个简单的 Java 应用程序,可显示当前和以前的按键操作。 安装 如果您使用的是 Windows,请确保安装了 。 从命令行/终端上的keypress-parade目录中,输入以下内容来编译代码: $ javac -d . @...
python库,解压后可用。 资源全名:parade_crossfilter-0.0.1-py3-none-any.whl
资源来自pypi官网。 资源全名:parade_crossfilter-0.0.1-py3-none-any.whl
介绍 PARADE是一个周期精确的全系统仿真平台,用于... git clone https://github.com/cdsc-github/parade-ara-simulator.git 设置要求 目前,PARADE已在两个64位平台上进行了测试: CentOS版本6.6(最终版)和CentOS版
AngularParade 该项目是使用版本1.7.3生成的。开发服务器为开发服务器运行ng serve 。... 如果您更改任何源文件,该应用程序将自动重新加载。代码脚手架运行ng generate component component-name生成一个新的组件。...
parade20
Zebra Parade
阅兵式 关于路由器的一个项目路由器和上下文
从上下文菜单中选择RGB Parade灯以在子脉冲中显示RGB Parade。※在Web的规格上,只有同一服务器上的图像可以显示RGB Parade。※如果不希望连续成功,请用映像单击图像并使用图像将焦点移动到图像,然后打开上下文...
它在生产模式下正确捆绑了React,并优化了构建以获得最佳性能。 生成被最小化,并且文件名包括哈希值。 您的应用已准备好进行部署! 有关更多信息,请参见关于的部分。 yarn eject 注意:这是单向操作。 eject ...
quickstart 源码目录介绍 ./js ├── base // 定义游戏开发基础类 │ ├── animatoin.js // 帧动画的简易实现 │ ├── pool.js // 对象池的简易实现 │ └── sprite.js // 游戏基本元素精灵类 ...