【洛谷】【动态规划+单调队列】P1725 琪露诺
【题目描述:】
在幻想乡,琪露诺是以笨蛋闻名的冰之妖精。
某一天,琪露诺又在玩速冻青蛙,就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多,在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为0到N,琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动,当她在格子i时,她只移动到区间[i+l,i+r]中的任意一格。你问为什么她这么移动,这还不简单,因为她是笨蛋啊。
每一个格子都有一个冰冻指数A[i],编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时,获取最大的冰冻指数,这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了,所以她决定拜托你帮它决定怎样前进。
开始时,琪露诺在编号0的格子上,只要她下一步的位置编号大于N就算到达对岸。
【输入格式:】
第1行:3个正整数N, L, R
第2行:N+1个整数,第i个数表示编号为i-1的格子的冰冻指数A[i-1]
【输出格式:】
一个整数,表示最大冰冻指数。保证不超过231-1
[算法分析:]
一道典型的DP题,已知a[i]为点i的冰冻指数,设f[i]为到达点i时获得的最大冰冻指数
则f[i]的状态是由f[i+l, i+r]转移来的
即f[r]的状态是由f[i-r, i-l]得到的.
可以求得状态转移方程:
f[i] = max{f[i - j]} + a[i]
l <= j <= r <= i
时间复杂度为O(n2),n ≤ 200000 的范围显然是超时了.
考虑如何优化:
显然对于求max{f[i - j]}的过程是可以优化的,
用优先队列或者线段树?O(n log2 n)确实是一个很优秀的复杂度,但是还有更优的:
单调队列,时间复杂度为O(n).
每次把一个f[p]值放入deque中,维护序列的单调性(从大到小),
但如果某一次队头的元素的坐标已经不足以跳到当前点了,就要把队首pop出去
所以deque中存放的应是一个结构体或者pair.
那有没有可能在pop队尾的时候把之后的最优解pop掉呢?
现在要加入队列的元素坐标一定比队尾元素要大,而其值也比需要被pop掉的队尾元素大,
所以最优解不管怎么pop都会在队列里。
[Code:]
//P1725 琪露诺
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; const int MAXN = + ; int n, l, r;
int a[MAXN];
int f[MAXN];
struct Node {
int v, num;
}; deque<Node> q; inline int read() {
int x=, f=; char ch=getchar();
while(ch<'' || ch>'') {
if(ch == '-') f = -;
ch = getchar();
}
while(ch>='' && ch<='')
x=(x<<)+(x<<)+ch-, ch=getchar();
return x * f;
} int main() {
n = read(), l = read(), r = read();
for(int i=; i<=n; ++i)
a[i] = read();
int p = ;
for(int i=l; i<=n; ++i) {
// 求max{f[i-r, i-l]}
// int maxn = 1 << 31;
// int s = i-r<0 ? 0 : i-r;
// for(int j=s; j<=i-l; ++j)
// maxn = max(maxn, f[j]);
while(!q.empty() && q.back().v < f[p])
q.pop_back();
q.push_back((Node){f[p], p});
while(q.front().num + r < i) q.pop_front();
f[i] = q.front().v + a[i];
++p;
}
int ans = << ;
for(int i=n-r+; i<=n; ++i)
ans = max(ans, f[i]);
printf("%d\n", ans);
}
最新文章
- Linux 学习记录
- url 处理
- java io流(字节流)复制文件
- map与vector---Email Aliases
- VMware共享目录设置
- hdu 4046 Panda 树状数组
- Umbraco(3) - CSS &; Javascript(翻译文档)
- 判断一个值是不是DBNull.Value
- Java常用类之要点总结
- Headless Chrome:服务端渲染JS站点的一个方案【中篇】【翻译】
- Codeforces Round#403 (Div. 1)
- How tomcat works 读书笔记十二 StandardContext 下
- 项目群MSP课程最大的特点
- Linux下如何查看版本
- 【LOJ#2542】[PKUWC2018]随机游走(min-max容斥,动态规划)
- nodejs创建文件
- JavaEE学习总结(十二)—MyEclipse开发工具与HTML
- 30 个java编程技巧(最佳实践的初学者)
- 第三篇:jmeter的作用域和执行顺序
- 安装torch-opencv