题解【洛谷P1725】琪露诺

题面

典型的单调队列优化\(\text{DP}\)题。

不难想到设\(dp_i\)表示以\(i\)结尾能得到的最大冰冻指数。

这样设的转移方程也很简单：\(dp_i=\max\left\{ dp_j+a_i \right\} (i ? r ≤ j ≤ i ? l)\)。

然而这样做的时间复杂度是\(\Theta(n^2)\)的，只有\(60\)分。

考虑如何优化。

我们可以利用单调队列这一个数据结构来维护\(dp_j\)的最大值。

此时的决策点就是队首点。

这就是单调队列优化\(\text{DP}\)。

#include <bits/stdc++.h>
#define itn int
#define gI gi

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int maxn = 200003;

int n, m, l, r, a[maxn], q[maxn], p[maxn], head = 1, tail, dp[maxn];

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi(), l = gi(), r = gi();
    for (int i = 0; i <= n; i+=1) a[i] = gi(); //注意从0开始
    memset(dp, 0xcf, sizeof(dp)); //设为无穷小值
    int ans = dp[0], now = 0; //答案和当前进入队列的编号
    dp[0] = 0;
    for (int i = l; i <= n; i+=1) //注意从l开始循环
    {
        while (head <= tail && dp[q[tail]] <= dp[now]) --tail; //单调队列中的队尾出队
        q[++tail] = now; //将这个点加入队列
        while (q[head] < i - r) ++head; //判断不合法的区间
        dp[i] = dp[q[head]] + a[i]; //状态转移
        ++now; //注意增加进入队列的编号
    }
    for (int i = n - r + 1; i <= n; i+=1) ans = max(ans, dp[i]); //答案取max
    printf("%d\n", ans);
    return 0;
}

题解【洛谷P1725】琪露诺

原文：https://www.cnblogs.com/xsl19/p/12261690.html