题解 P1725 【琪露诺】
smilke
·
·
题解
Update 6.8
原来的做法已更新，并且更新了单调队列做法。
最后两组数据会WA，主要是因为没有判断DP状态的转移是否合法，如果该点是不能到达的，那么就不能用它更新后面的状态。
用一个数组use[i]标记一下f[i]的合法性就可以了。
这是一道DP优化入门的好题。
读懂题意后，我们很容易想到这道题的状态以及转移。
设f[i]表示跳到第i个格子的最优值。
初始状态：f[0]=0，表示在原点的价值为0.
状态转移：f[i]=max{f[j]+a[i]} (j\in[i-r,i-l]).
最终状态：max(f[n+1]....f[n+l]).(因为琪露诺最终跳到的区间范围是[n+1,n+l]).
于是我们就能拿到暴力的部分分。
考虑优化，我们发现，f[i]的取值只能由决策区间[i-r,i-l]转移而来，而a[i]是定值，所以我们只用考虑f[i-r].... f[i-l]的最优决策.
由DP的转移方程告诉我们，我们需要求的是决策的最大值。
那么我们自然地可以想到，用一种数据结构去维护决策的最优。
结合题目的情况，即：
$[i-l+1,i-r+1]$的决策影响状态$f[i+1]$的最大值。
每个$f[i]$相对应的是一个决策区间，而区间移动的长度是固定的，这不禁让人想到滑动窗口这道题，我们可以通过动态维护区间的最大值，从而节省一维枚举决策的时间。
维护区间最值可以用优先队列或者单调队列。
上面两种方式都能过，我们可以比较一下两种做法。
首先说优先队列的做法，对于堆里的元素我们需要用一个$vis[i]$数组来表示是否在队列里，然后看看堆里维护的区间是否超出了决策区间，删除堆顶元素直到符合条件为止。
每次移动的操作时间复杂度为$O(logn)$，所以总时间复杂度为$O(nlogn)$.
以下为代码：
```cpp
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e6+50;
int n,l,r,a[N],f[N],vis[N],ans=-1e9,use[N];//use[i]标记f[i]是否合法
priority_queue< pair<int,int> > q;
int main(){
scanf("%d%d%d",&n,&l,&r);
rep(i,1,2*n) f[i]=-1e9;
rep(i,0,n) scanf("%d",&a[i]);
rep(i,l,r) use[i]=1;
rep(i,0,n){
if(i<l) {q.push(mp(-1e9,0));f[i+l]=a[i+l];continue;}
int y=q.top().second;
if(i-r+l-1>=0) vis[i-r+l-1]=1;
while(vis[y]||!use[y]) { q.pop(); if(q.empty()) break; y=q.top().second;} //删除堆顶不合法的决策
q.push(mp(f[i],i));
f[i+l]=q.top().first+a[i+l];
if(use[i]) use[i+l]=1;
}
rep(i,n+1,n+l) if(use[i]) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
```
类似的，我们也可以只维护一个单调递减的队列，每次决策的时候取出队头即为最优决策，省去了之前入堆的$log$（STL自带的$log$）。
由于每个状态只进出队一次，故总时间复杂度为$O(n)$.
以下为代码：
```cpp
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e6+50;
int n,l,r,a[N],f[N],vis[N],ans=-1e9,use[N],q[N],L,R;
int main(){
scanf("%d%d%d",&n,&l,&r);
rep(i,1,2*n) f[i]=-1e9;
rep(i,0,n) scanf("%d",&a[i]);
rep(i,l,r) use[i]=1;
rep(i,0,n){
while(L<=R&&f[i]>f[q[R]]) R--;//维护的是单调递减的队列
q[++R]=i;
while(L<=R&&q[L]<i-r+l) L++;//合法的区间转移范围
f[i+l]=f[q[L]]+a[i+l];
if(use[i]) use[i+l]=1;
}
rep(i,n+1,n+l) if(use[i]) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
```
可以发现，对于区间移动的最值，单调队列明显比优先队列好写，并且好维护，时间复杂度少一个$log$。
所以对于区间移动的最值问题，单调队列是一个非常好的解法。
（~~比STL的优先队列维护不知高到哪里去了~~）