题面:
题面有点长，不想粘了，QAQ。
题解：
一句话题意，你有 \(n\) 件物品需要依次放进去，每个物品放进去之后会得到一定的权值，为当前锅炉里面的物品的数量乘以 \(a_i\)
每次在放这件物品之前，你可以那出 \(0-s\) 件物品出来，但锅炉里物品的数量不能超过 \(w\)
\(dp\) 状态应该很好想。
设$ f[i][j]$ 表示放 第 \(i\) 件有 \(j\) 个物品在锅炉里的最大价值。
那么就可以有前一天的状态转移过来。
则有 \(f[i][j] = max(f[i-1][k] + j * a[i])\)
以及不拿出来的情况 \(f[i][j] = max(f[i-1][j-1])\)
然后你就可以拿到 \(85\) 分的好成绩，大雾
我们考虑一下优化，发现后面的那段柿子是个很经典的求一段区间的最小值的形式。
那我们就可以采用一下单调队列优化一下。
注意枚举 \(k\) 的时候要倒着枚举，因为你 用到的是 \(j\) 之后得状态，要先把他 \(f[i-1]\) 后面的状态先入队。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
int n,w,s,head,tail,a[5560],f[5560][5560],q[5560];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
signed main()
{
n = read(); w = read(); s = read(); int ans = -1e13;
for(int i = 1; i <= n; i++) a[i] = read();
memset(f,128,sizeof(f));
f[1][1] = a[1];
for(int i = 2; i <= n; i++)
{
head = 1, tail = 0;
for(int j = w; j >= 1; j--)
{
f[i][j] = max(f[i][j],f[i-1][j-1] + j * a[i]);//不放的情况
while(head <= tail && q[head] > min(w,j+s-1)) head++;//单调队列优化一下
while(head <= tail && f[i-1][q[tail]] <= f[i-1][j]) tail--;
q[++tail] = j;
f[i][j] = max(f[i][j],f[i-1][q[head]] + j * a[i]);
}
}
for(int i = 1; i <= w; i++) ans = max(ans,f[n][i]);
printf("%lld\n",ans);
return 0;
}
