求条 单调队列5分

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5009],f[5009][5009];
int q[5009],F,r;
signed main()
{
    int n,w,s;
    cin>>n>>w>>s;
    for(int i=1;i<=n;i++)cin>>a[i];
    memset(f,0x80,sizeof f); //10000000100000001000000010000000
    //f[i][j]表示第i个物品处理完成后，锅中有j个原料的最大耐久
    f[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        F=0,r=1;
        q[1]=w;
        for(int j=1;j<=min(i,w);j++)
        {
            //拿完后有j-1个
            //最多拿出s个，j+s-1
            //不能超w，min(j+s-1,w)为上限，j-1为下限
            //考虑使用单调队列优化dp
            //每次都把队列清空
            while(F<r&&q[F+1]>min(j+s-1,w))F++;
            while(F<r&&f[i-1][q[r]]<=f[i-1][j-1])r--;
            q[++r]=j-1;
            f[i][j]=f[i-1][q[F+1]]+a[i]*j;
        }
    }
    cout<<*max_element(f[n],f[n]+w+1);
}