A
模板题

最小值：每次放入左标，并判断进入的元素是否大于尾部元素
最大值：类似

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
deque<int>q;
int n, k;
int a[N];
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        if (!q.empty() && i - q.front() >= k)
            q.pop_front();
        while (!q.empty() && a[q.back()] > a[i])
            q.pop_back();
        q.push_back(i);
        if (i >= k)cout << a[q.front()] << " ";
    }
    cout << endl;
    while (!q.empty())
    {
        q.pop_front();
    }
    for (int i = 1; i <= n; i++)
    {
        if (!q.empty() && i - q.front() >= k)
            q.pop_front();
        while (!q.empty() && a[q.back()] < a[i])
            q.pop_back();
        q.push_back(i);
        if (i >= k)cout << a[q.front()] << " ";
    }
    return 0;
}

B（csdn题解思路）
dp+滑动窗口优化

1.我们设f[i][j]表示加完第i种原料后还剩j种原料的最大耐久度之和，
我们来看看f[i][j]可以由哪些状态来转移得到，很显然它是由加完第i-1种原料的一些状态得到的，
现在我们来想想应该加完第i-1种原料剩下多少种原料才能转移得到f[i][j]呢？


----------


f[i][j],f[i-1][j](加上i-1中原料)，f[i][j-1]是当取i时候取到
我们可以先去掉一种原料然后再加上第i种原料，依次类推，f[i-1][j-1+s]也可以
f[i-1][j-1+s]的意思是去掉之前的s种原料并且取到当前i的原料
注意的是我们不能使剩余的原料个数大于w（因此在w和j-1+s取min）

1.先找状态表示f[i][j]
f[i][j-1]是i原料取到
f[i-1][j]，加上i-1中原料
这是超时的代码（n^3）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 10;
ll f[N][N];//f[i][j]表示放完第i种原料后锅内还有j种原料的最大耐久度之和 
ll a[N];
int main()
{
    int n, w, s;
    cin >> n >> w >> s;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= min(w, i); j++)
            for (int k = j - 1; k <= min(w, j - 1 + s); k++)
                f[i][j] = max(f[i][j], f[i - 1][k] + a[i] * j);
    }
    ll ans = -0x3f3f3f3f;
    for (int i = 1; i <= w; i++)
        ans = max(ans, f[n][i]);
    printf("%lld", ans);
    return 0;
}

注意：上述代码会超时，因为三重for循环，所以复杂度太高，
现在我们来看看能不能对这道题目进行一下优化，我们先来看一下最里面的一层for循环，
就是枚举f[i-1][j-1~j-1+s]然后找一个最大值，但是这个找最大值的过程我们是o(n)的，
而且这个过程我们需要遍历多次，
有没有发现这个问题似曾相识，就是滑动窗口的那个问题，
每次给定一个窗口的范围，然后找这个窗口的最大值或者最小值

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 10;
ll q[N], tt, hh;
ll f[N][N];//f[i][j]表示放完第i种原料后锅内还有j种原料的最大耐久度之和 
ll a[N];
int main()
{
    int n, w, s;
    cin >> n >> w >> s;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        hh = tt = 0;//一定不要忘记初始化
        for (int j = 1, k = 0; j <= min(w, i); j++)//单调队列优化 
        {
            while (k <= min(w, j - 1 + s))//把更新f[i][j]的f[i-1][k]全部入队列
            {
                while (hh < tt && f[i - 1][q[tt]] <= f[i - 1][k]) tt--;
                q[++tt] = k++;
            }
            while (hh < tt && q[hh + 1] < j - 1) hh++;
            f[i][j] = f[i - 1][q[hh + 1]] + a[i] * j;
        }
    }
    ll ans = -0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= w; i++)
        ans = max(ans, f[n][i]);
    printf("%lld", ans);
    return 0;
}