题解 P1725 【琪露诺】

· · 题解

使用deque实现的单调队列优化DP

（看了一眼题解里还没有利用双端队列容器实现的单调队列，求通过）

更好的阅读体验点这里：博客传送门

关于单调队列的deque实现：戳

一道典型的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(n^2)，n ≤ 200000 的范围显然是超时了.

考虑如何优化：

显然对于求max\{f[i - j]\}的过程是可以优化的，

用优先队列或者线段树？O(n log_2 n)确实是一个很优秀的复杂度，但是还有更优的：

单调队列，时间复杂度为O(n).

每次把一个f[p]值放入deque中，维护序列的单调性（从大到小），

但如果某一次队头的元素的坐标已经不足以跳到当前点了，就要把队首pop出去

所以deque中存放的应是一个结构体或者pair.

那有没有可能在pop队尾的时候把之后的最优解pop掉呢？

现在要加入队列的元素坐标一定比队尾元素要大，而其值也比需要被pop掉的队尾元素大，

所以最优解不管怎么pop都会在队列里。

[Code:] 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN = 200000 + 1;

int n, l, r;
int a[MAXN];
int f[MAXN];
struct Node {
    int v, num;
};

deque<Node> q;

inline int read() {
    int x=0, f=1; char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch>='0' && ch<='9')
        x=(x<<3)+(x<<1)+ch-48, ch=getchar();
    return x * f;
}

int main() {
    n = read(), l = read(), r = read();
    for(int i=0; i<=n; ++i)
        a[i] = read();
    int p = 0;
    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 = 1 << 31;
    for(int i=n-r+1; i<=n; ++i)
        ans = max(ans, f[i]);
    printf("%d\n", ans);
}