题解 P1725 【琪露诺】

zeromaker · 2015-10-12 11:24:34 · 题解

虽然比赛的时候也是用单调队列水过去的，但是作为C党，这题事实上可以用两个优先队列水过去，虽然复杂度变成了O（nlogn），但是对于本题还是可以接受的。

dp方程很简单，dp[i]=max（dp[k]）（k>=i+ll && k<=i+rr）+arr[i]，如果K没有限制的话只需要把所有的数扔到一个优先队列里，每次取最小的就可以了，但是关键是k是在[i+ll,i+rr]范围内，这时候我们只需要维护第二个优先队列，这个多出来的优先队列的意义是：删除，每次把第一个优先队列当中的最大值取出，再把第二个优先队列当中的最大值取出，如果这两个数一样，说明这次取出的最优解事实上是走不到的（即之前已经被删除了），这时候就把两个优先队列往后弹，弹到不一样为止，就取出了范围内的最大值，加上arr[i]即可。然后每次再把超出范围的数加入到删除队列当中，把添加的添加到添加队列中，问题就解决了

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#include<queue>
using namespace std;

const int Maxn=200010;
priority_queue<int> q1,q2;
int n,ll,rr;
int arr[Maxn],dp[Maxn];

int main()
{
    scanf("%d%d%d",&n,&ll,&rr);
    n++;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
        dp[i]=arr[i];
    }
    for (int i=n-ll;i>=1;i--)
    {
        int x1=0,x2=0;
        q1.push(dp[i+ll]);
        if (i<n-rr)
            q2.push(dp[i+rr+1]);
        if (q2.empty())
        {
            x1=q1.top();
        }
        else
        {
            x1=q1.top();
            x2=q2.top();
        }
        while (x1==x2 && !q2.empty())
        {
            x1=q1.top();
            x2=q2.top();
            q2.pop();
            q1.pop();
        }
        if (i>n-rr)
        {
            dp[i]=max(dp[i],dp[i]+x1);
        }
        else
        {
            dp[i]=dp[i]+x1;
        }
    }
    printf("%d\n",dp[1]);
}