HDU 2490 Parade(DPの单调队列)(2008 Asia Regional Beijing)
Description
When seeing his Citizens, Panagola always waves his hands. He may get tired and need a break. So please never make Panagola travel in a same west-east road for more than k minutes. If it takes p minutes to pass a love-hate zone, we say the length of that love-hate zone is p. Of course you know every love-hate zone’s length.
The figure below illustrates the case in sample input. In this figure, a best route is marked by thicker lines.
Input
The first line contains three integers: n, m and k.(0<n<=100,0<m<=10000, 0<=k<=3000000)
The next n+1 lines stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the welcome values of the road’s m love-hate zones, in west to east order.
The last n+1 lines also stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the lengths (in minutes) of the road's m love-hate zones, in west to east order.
Output
题目大意:有一个n*m的矩阵,只能沿着边走,只能往左、往右或往上走,在同一行只能沿一个方向走(走了左边就不能返回走右边了)。打横的边都有一个权值(可能为负数)和一个长度,每行走过的长度不能超过k,打竖的边没有权值和长度。先要从最下面的任意一个点开始,走到最上面的任意一个点,问最大权值和为多少(答案不超过$2^{31}-1$,虽然题目不是这么说的)。
思路:一看就是动态规划,每一行只和上一行的状态有关。因为习惯从小到大循环我们从上往下走,反正都一样。设dp[i][j]为走到第 i 行第 j 个点的最大权值(已往左往右走完),那么dp[i][j] = max(dp[i-1][x] + sum(welcome[i][y])),distance(x, y) ≤ k,y in [x, i]。其中distance和sum(welcome[i][y])可以预处理出来(如sum[i]代表1~i的和,distance(i, j) = sum[j] - sum[i],i ≤ j),平均到处理每个dp[i][j]身上时间复杂度为O(1)。但是这样计算dp数组,时间复杂度高达$O(nm^2)$。
现假设我们从左到右走,那么dp[i][j] = max(dp[i - 1][x] - sum_welcome[x] + sum_welcome[y]) = dp[i][j] = max(dp[i - 1][x] - sum_welcome[x]) + sum_welcome[y],那么对每一个j,所用的dp[i - 1][x] - sum_welcome[x]都是一样的,这里很容易能想到单调队列优化(如果你知道单调队列的话)。每次把队列末尾小于dp[i - 1][j] - sum_welcome[j]弹出,把队头distance(i, x) > k的弹出,队头就是最佳的dp[i - 1][x] - sum_welcome[x]。优化完时间复杂度为$O(nm)$,已经是读入数据的复杂度了。(这里不介绍单调队列)
PS:可恶这题居然不让人在线非要我把整个矩阵一起读进来……
代码(1078MS,可恶啊C++又比G++快一倍):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int MAXN = ;
const int MAXM = ; int wel[MAXN][MAXM], len[MAXN][MAXM];
int sum_w[MAXM], sum_l[MAXM];
int a[MAXM], b[MAXM], head, tail;
int dp[][MAXM];
int n, m, k, cur; inline void insert(int x, int y) {
while(head != tail && a[tail - ] < x) --tail;
a[tail] = x; b[tail] = y; ++tail;
} void solve() {
memset(dp, , sizeof(dp));
cur = ;
for(int i = ; i < n; ++i) {
cur ^= ;
memset(dp[cur], , sizeof(dp[cur])); sum_w[] = sum_l[] = ;
for(int j = ; j <= m; ++j) sum_w[j] = sum_w[j - ] + wel[i][j];
for(int j = ; j <= m; ++j) sum_l[j] = sum_l[j - ] + len[i][j];
head = tail = ;
for(int j = ; j <= m; ++j) {
insert(dp[cur ^ ][j] - sum_w[j], sum_l[j]);
while(k < sum_l[j] - b[head]) ++head;
dp[cur][j] = max(dp[cur][j], a[head] + sum_w[j]);
} sum_w[m] = sum_l[m] = ;
for(int j = m; j > ; --j) sum_w[j - ] = sum_w[j] + wel[i][j];
for(int j = m; j > ; --j) sum_l[j - ] = sum_l[j] + len[i][j];
head = tail = ;
for(int j = m; j >= ; --j) {
insert(dp[cur ^ ][j] - sum_w[j], sum_l[j]);
while(k < sum_l[j] - b[head]) ++head;
dp[cur][j] = max(dp[cur][j], a[head] + sum_w[j]);
}
}
} int main() {
while(scanf("%d%d%d", &n, &m, &k) != EOF) {
if(n == && m == && k == ) break;
++n;
for(int i = ; i < n; ++i)
for(int j = ; j <= m; ++j) scanf("%d", &wel[i][j]);
for(int i = ; i < n; ++i)
for(int j = ; j <= m; ++j) scanf("%d", &len[i][j]);
solve();
int ans = ;
for(int i = ; i <= m; ++i) ans = max(ans, dp[cur][i]);
printf("%d\n", ans);
}
}
最新文章
- 【EF学习笔记10】----------主从表级联操作
- WebService到底是什么?
- JS的循环、复杂运算符
- 【Origin】 碑铭
- C++三种内存分配方式
- PHP json_encode中日语问题
- Nodejs in Visual Studio Code 14.IISNode与IIS7.x
- Cross Product
- CSS的继承性和层叠性
- Java 使用Arrays.sort排序 从大到小排列
- 来测试下你的Java编程能力
- python实现单线程多任务非阻塞TCP服务端
- Kinect2.0点云数据获取
- 学JS的心路历程-函式(二)arguments
- 如何提升RDS响应速度
- Ubuntu14.04下安装eclipse
- jQuery.Validator Sample
- powerdesigner与mysql数据库的连接
- 不再为命名而苦恼!使用 MSTestEnhancer 单元测试扩展,写契约就够了
- 点击checkbox全选,其它被选中,再点击取消