洛谷题单指南-动态规划2-P1725 琪露诺

原题链接：https://www.luogu.com.cn/problem/P1725

题意解读：走过一系列格子之后，冰冻指数之和最大，相当于计算最大子序列的和。

解题思路：

设a[0~n]保存所有冰冻指数

设dp[i]表示以第i号格子为终点所能获得的最大冰冻指数

设j表示i的前一个格子，也就是从j可以移动到i

已知i，则j的范围也很好计算，由于每次在x移动的范围是 x + l ~ x + r之间，所以上一步j的范围是i-r ~ i-l

然后计算dp[j] + a[i]的最大值即可

所以有dp[i] = max(dp[i], dp[j] + a[i])，j取i-r ~ i-l之间，注意j不能小于0

由于冰冻指数有负数，在加法过程中会出现负值，最后要计算最大值，dp的初始化需要小心

看数据范围：-2×10^5≤N≤2×10^5，−10^3≤Ai​≤10^3

所以所有数相加最小是-2×10^8，最大是2×10^8

dp初始化为-1e9就可以，注意千万不要初始化为INT_MIN，这样在做加法时如果加一个负数就会溢出

最后，遍历dp，找到下一步的位置大于n的取最大值。

80分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int a[N]; //冰冻指数
int dp[N]; //dp[i]表示以第i号格子为终点所能获得的最大冰冻指数
int n, l, r;

int main()
{
    cin >> n >> l >> r;
    for(int i = 0; i <= n; i++) 
    {
        cin >> a[i];
        dp[i] = -1e9; //由于有负数，dp初始化为-1e9,注意不能初始化为INT_MIN，因为再加负数会溢出
    }
    dp[0] = 0; //0号格子可获得0冰冻指数
    for(int i = 1; i <= n; i++) //第一个可到达的格子是l
    {
        for(int j = i - r; j <= i - l; j++) //i的上一个格子范围在i-r~i-l之间
        {
            if(j < 0) continue;
            dp[i] = max(dp[i], dp[j] + a[i]);
        }
    }
    int ans = INT_MIN;
    for(int i = 0; i <= n; i++) 
    {
        if(i + r > n) //下一步的位置编号大于n才算到达对岸
            ans = max(ans, dp[i]);
    }
    cout << ans;

    return 0;
}

以上代码的复杂度为O(n^2)，最坏情况下是会超时的，必须做出优化。

这里的优化点在于，对于每一个i，要在j = i-r ~ i-l范围内计算dp[j] + a[i]的最大值，也就是找一个范围是i-r ~ i-l窗口内的最大值。

于是，想到了单调队列，只需要在i>=l之后（l之前0之后的位置都无法走到），开始维护窗口大小是r - l + 1的单调递减队里即可快速获取i-r ~ i-l窗口内的最大值。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int a[N]; //冰冻指数
int dp[N]; //dp[i]表示以第i号格子为终点所能获得的最大冰冻指数
int q[N]; //单调队列，存dp的下标
int n, l, r;

int main()
{
    cin >> n >> l >> r;
    for(int i = 0; i <= n; i++) 
    {
        cin >> a[i];
        dp[i] = -1e9; //由于有负数，dp初始化为-1e9,注意不能初始化为INT_MIN，因为再加负数会溢出
    }
    dp[0] = 0; //0号格子可获得0冰冻指数
    q[0] = 0; //队列加入一个元素，是dp的下标0
    int head = 0, tail = 0; //队首、队尾
    for(int i = l; i <= n; i++) //i第一个可走的位置是l，右边界正好是0
    {
        dp[i] = dp[q[head]] + a[i]; //直接取窗口内的最大值，即队首元素对应的值
        //下一个要放入队列的下标是右边界加1：i - l + 1
        if(head <= tail && i - l + 1 - q[head] > r - l) head++; //如果队列元素将超过窗口大小，队首出队
        while(head <= tail && dp[q[tail]] <= dp[i - l + 1] ) tail--; //如果队尾元素对应的dp值不比dp[i-r+1]大，则出队，确保单调递减
        q[++tail] = i - l + 1;
    }
    int ans = INT_MIN;
    for(int i = 0; i <= n; i++) 
    {
        if(i + r > n) //下一步的位置编号大于n才算到达对岸
            ans = max(ans, dp[i]);
    }
    cout << ans;

    return 0;
}