P1725 琪露诺 题解返回题目

首先么，一个dp，对不对，这个很简单。

f[i]=max{fk}+a[i];

但是纯dp肯定会超时，那么就要优化咯；

楼下的同学们已经指明了优化方法

1.单调队列

2.优先队列（大根堆）

个人更喜欢单调队列，不过嘛，优先队列也是值得学习的。

我这里给出用优先队列的程序，思想嘛，就是一个堆记录从1~i-L的max；另一个记录从1~i-R-1的max；

是不是把两个堆重复的部分删掉，就是i-L~i-R了，这一部分就是纯dp时需要枚举的k啊；

当然咯，我们只需要判断两个堆的max是否相同，相同了说明出现重复，把堆顶弹出就好了；

但是，如果出现所有的数据都一样怎么办呢，只要再用结构体把下标也放进去就好了；

当然，洛谷数据没有相同。。。。。那就怎么简单怎么来吧

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int>q1,q2;
int n,R,L,ans;
int a[200010],f[200010];
int main()
{
? ? scanf("%d%d%d",&n,&L,&R);
? ? for(int i=0;i<=n;i++)scanf("%d",&a[i]);
? ? for(int i=1;i<L;i++)q2.push(a[i]);
? ? for(int i=L;i<=n;i++){
? ? ? ? q1.push(f[i-L]);
? ? ? ? if(i-R-1>=L)q2.push(f[i-R-1]);
? ? ? ? while(!q2.empty()&&q1.top()==q2.top()){
? ? ? ? ? ? q1.pop();q2.pop();
? ? ? ? }
? ? ? ? f[i]=q1.top()+a[i]; ? ? ? ? ? ?
? ? }
? ? for(int i=n-R+1;i<=n;i++)ans=max(ans,f[i]);
? ? printf("%d",ans);
}