单调队列

https://www.cnblogs.com/ljy-endl/p/11638389.html
本次是看这个教程学习的

什么时候用单调队列？

在一个数列中，求多个区间的最值。比如求数列a[]中每个数之前m个数中的最小值。

正常来说这是n*m的复杂度，但单调队列就可以将其优化为n的复杂度

算法核心浅析（以求区间最小值为例）

给定数列a[n]，求每个数前m个数的最小值。

准备一个队列，队首和队尾都能出队，仅队尾可以入队。队列中存储a[]中下标。

遍历i=1~n

每次首先打印队头，然后根据条件弹出：（弹出均用while）

队头弹出条件：q[head]<i-m+1 因为往后这个队头都不会再用到了，它永远是m个以前

队尾弹出条件：a[q[tail]]>a[i] 这意味着i优于q[tail]，有个隐藏条件i>q[tail]，即i一定比q[tail]更晚从队头弹出，同时i这个答案又优于q[tail]，理所应当q[tail]要滚蛋

结尾把i入队

（以上建议直接看上面附的链接教程）

---

事实上这个队列符合一下条件：单调。q[]是单调的，a[q[]]也同样是单调的。前者因着我们入队顺序而单调，后者因着我们队尾弹出条件而单调。而队头的弹出保证我们要求的最值是在“前m”这个范围中。

这个算法的本质其实是让我们求的最值能最大化利用起来。

要记住的一点是，单调队列是那个队列单调，而要求不是a[]这个原本的数列单调。

优化DP

从P5858这道题我们能学到的是：

1 为什么j从后往前推
答：因为dp[i][j]要从dp[i-1][j-1~min(w,j-1+s)]中找最值，整个数列是dp[i-1][]

我们把dp[][]画出来

上面是dp[i-1][]，下面是dp[i][]箭头意味着dp[i-1][]中的某个区间里产生dp[i][]中某个位置的答案

这个题目和之前简单的求区间最小值有什么区别？求区间最小值是求哪个位置的答案，就在之后把那个位置入队——因为它是求前m个。

而这里呢，是求前1个，它自己，和后面若干个。肯定在求的时候这些位置都要已经入队了才好。

这样你想想，如果从前面推的话，你得提前入队好几个。不如从后面推，只需要提前入队一个就好。

重点是：求之前要保证答案所在的区间全部入队过

代码：

#include<iostream>
#include<cstring>
using namespace std;
const long long N=5007;
long long MAXN=1008600110086001;
long long n,s,w;
long long a[N],monoQ[N];
long long dp[N][N];
void input(){
    cin>>n>>w>>s;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
}
void fun(){
    for(long long i=0;i<=n;i++) for(long long j=0;j<=w;j++) dp[i][j]=-MAXN;
    dp[0][0]=0;
    for(long long i=1;i<=n;i++){
        long long l=1,r=1;
        monoQ[l]=w;
        for(long long j=w;j;j--){
            while(l<=r&&monoQ[l]>j-1+s){
                l++;
            }
            while(l<=r&&dp[i-1][monoQ[r]]<dp[i-1][j-1]){
                r--;
            }
            monoQ[++r]=j-1;
            dp[i][j]=dp[i-1][monoQ[l]]+a[i]*j;
        }
    }
}
void output(){
    long long ans=-MAXN;
    for(long long j=1;j<=w;j++){
        ans=max(ans,dp[n][j]);
    }
    cout<<ans;
}
int main(){
    input();
    fun();
    output();
    return 0;
}