题目链接:uva 1427 - Parade
题目大意:F城由n+1各横向路和m+1个竖向路组成。你的任务是从最南边的路走到最北边的路,使得走过的路上的高兴值和最大(高兴值可能为负值)。同一段路不能经过两次,且不能从北往南走。另外在每条横路上所花费的时间不能超过k。
解题思路:dp[i][j][0]表示走到(i,j)这个位置的最大开心值和,dp[i][j][1]表示从左边移动到(i,j)的最优值,dp[i][j][2]表示从右边移动到(i,j)的最优值。
dp[i][j][1] = min { dp[i-1][k][0] + gay[i][j][1] - gay[i][k][1] | dis[i][j][1] - dis[i][k][1] <= k }
dp[i][j][1] = min { dp[i-1][k][0] + gay[i][j][2] - gay[i][k][2] | dis[i][j][2] - dis[i][k][2] <= k }
不过如果直接对于每个j考虑所有的k的话,复杂度为o(n*m^2),所以要加上单调队列优化。
dp[i-1][k][0] + gay[i][j][s] - gay[i][k][s] = gay[i][j][s] - (gay[i][k][s] - dp[i-1][k][0]);
令func(i, k, s) = gay[i][k][s] - dp[i-1][k][0]; 那么只要为护func的单调即可。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 105;
const int M = 1e4+10;
const int INF = 0x3f3f3f3f;
int n, m, k, h[M], d[M];
int gay[N][M][3], dis[N][M][3], dp[N][M][3];
void init () {
n++;
memset(gay, 0, sizeof(gay));
memset(dis, 0, sizeof(dis));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &h[j]);
gay[i][j][1] = gay[i][j-1][1] + h[j];
}
for (int j = m-1; j >= 0; j--)
gay[i][j][2] = gay[i][j+1][2] + h[j+1];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &d[j]);
dis[i][j][1] = dis[i][j-1][1] + d[j];
}
for (int j = m-1; j >= 0; j--)
dis[i][j][2] = dis[i][j+1][2] + d[j+1];
}
}
int func(int i, int j, int o) {
return gay[i][j][o] - dp[i-1][j][0];
}
int solve () {
int ans = -INF;
deque<int> que;
for (int i = 1; i <= n; i++) {
que.clear();
for (int j = 0; j <= m; j++) {
while (!que.empty() && dis[i][j][1] - dis[i][que.front()][1] > k) que.pop_front();
while (!que.empty() && func(i, que.back(), 1) >= func(i, j, 1)) que.pop_back();
que.push_back(j);
dp[i][j][1] = gay[i][j][1] - func(i, que.front(), 1);
}
que.clear();
for (int j = m; j >= 0; j--) {
while (!que.empty() && dis[i][j][2] - dis[i][que.front()][2] > k) que.pop_front();
while (!que.empty() && func(i, que.back(), 2) >= func(i, j, 2)) que.pop_back();
que.push_back(j);
dp[i][j][2] = gay[i][j][2] - func(i, que.front(), 2);
}
for (int j = 0; j <= m; j++)
dp[i][j][0] = max(dp[i][j][1], dp[i][j][2]);
}
for (int i = 0; i <= m; i++)
ans = max(ans, dp[n][i][0]);
return ans;
}
int main () {
while (scanf("%d%d%d", &n, &m, &k) == 3 && n + m + k) {
init();
printf("%d\n", solve());
}
return 0;
}
分享到:
相关推荐
灯塔游行一个Node.js命令行工具,可对域进行爬网并使用每个页面的灯塔性能数据来编译报告。为什么?有很多很棒的工具可以在单个网页上进行性能分析。我们都在使用和 。但是,如果您要评估整个站点的性能特征该怎么办...
parade-A data processing engine and service. 一个数据处理引擎和服务
Keypress Parade是一个简单的 Java 应用程序,可显示当前和以前的按键操作。 安装 如果您使用的是 Windows,请确保安装了 。 从命令行/终端上的keypress-parade目录中,输入以下内容来编译代码: $ javac -d . @...
泰克公司宣布Parade科技公司(Parade Technologies Inc.)成功使用泰克测试设备验证了其新型DP501 DisplayPort发送器对新兴DisplayPort标准的一致性要求。 DisplayPort作为视频电子标准协会(VESA)制订的一项新的...
AngularParade 该项目是使用版本1.7.3生成的。开发服务器为开发服务器运行ng serve 。... 如果您更改任何源文件,该应用程序将自动重新加载。代码脚手架运行ng generate component component-name生成一个新的组件。...
阅兵式 关于路由器的一个项目路由器和上下文
Create React App入门 该项目是通过引导的。 可用脚本 在项目目录中,可以运行: yarn start 在开发模式下运行应用程序。 打开在浏览器中查看它。 如果您进行编辑,则页面将重新加载。 您还将在控制台中看到任何...
python库,解压后可用。 资源全名:parade-0.1.10-py3-none-any.whl
python库。 资源全名:parade-0.1.14-py3-none-any.whl
资源来自pypi官网。 资源全名:parade-0.1.10-py3-none-any.whl
资源来自pypi官网。 资源全名:parade-0.1.20.6-py3-none-any.whl
quickstart 源码目录介绍 ./js ├── base // 定义游戏开发基础类 │ ├── animatoin.js // 帧动画的简易实现 │ ├── pool.js // 对象池的简易实现 │ └── sprite.js // 游戏基本元素精灵类 ...
python库,解压后可用。 资源全名:parade_crossfilter-0.0.1-py3-none-any.whl
资源来自pypi官网。 资源全名:parade_crossfilter-0.0.1-py3-none-any.whl
PARADE是一个周期精确的全系统仿真平台,用于加速器丰富的体系结构设计和探索。 它扩展了广泛使用的gem5仿真器,并提供了高级综合(HLS)支持。 如果您在研究中使用PARADE,请引用我们的ICCAD 15论文: 贾森·聪,...
parade20
Zebra Parade
从上下文菜单中选择RGB Parade灯以在子脉冲中显示RGB Parade。※在Web的规格上,只有同一服务器上的图像可以显示RGB Parade。※如果不希望连续成功,请用映像单击图像并使用图像将焦点移动到图像,然后打开上下文...