让我们继续练习dp
首先这道题约束条件很多
但实际上方程还是很好写的，f[i,j]表示第i天时拥有j只股票的最大收益
令p=max(0,i-k-1) 上一次较交易
易得f[i,j]=max(f[i-1,j],f[p,j-b]-ap[i]*b,f[p,j+s]+bp[i]*s) b<=as[i],s<=bs[i];
显然会TLE，我们要优化
f[i-1,j]我们可以先不管他，
我们令j1=j-b j2=j+s
则max(0,j-as[i])<=j1<=j
j<=j2<=min(m,j+bs[i]);
则原式可化为
f[i,j]=max(f[p,j1]+ap[i]*j1-ap[i]*j,f[p,j2]+bp[i]*j2-bp[i]*j)
观察得知对于当前的状态，结果只与j1,j2有关系
于是我们可以分开来对j1，j2求区间最大，再求一个总的最大就行
对此我们可以用线段树
但是，线段树算法O（n^2logn）而且实际常数较大，会TLE（一开始我就是这样）
观察区间其实总是整体右移的，这很像我一开始做的单调队列的滚动窗口那道题
于是我们可以用单调队列优化
加入只考虑买入的情况对于k1<k2
如果有f[p,k2]+ap[i]*k2>=f[p,k2]+ap[i]*k2 那么k2一定比k1优（更可能成为区间最大）
卖出情况同理，因此我们从0~m遍历一边，维护一个单调减的队列就行了
每个点最多出队一次，入队一次
因此复杂度为O(n^2);
const inf=-;
var q,b,s,ns,nb,vs,vb:array[..] of longint;
f:array[..,..] of longint;
l,ans,h,t,p,i,j,k,n,m:longint; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function compareb(x,y:longint):boolean;
begin
if f[p,x]+vb[i]*x>=f[p,y]+vb[i]*y then exit(true) else exit(false);
end; function compares(x,y:longint):boolean;
begin
if f[p,x]+vs[i]*x>=f[p,y]+vs[i]*y then exit(true) else exit(false);
end; begin
readln(n,m,k);
for i:= to n do
readln(vb[i],vs[i],nb[i],ns[i]);
for i:= to m do
f[,i]:=inf;
f[,]:=;
for i:= to n do
begin
p:=max(i-k-,);
h:=;
t:=;
q[]:=;
for j:= to m do //买入情况
begin
if j<> then
begin
while (h<t) and compareb(j,q[t]) do dec(t);
inc(t);
q[t]:=j;
end;
l:=max(,j-nb[i]);
while (q[h]<l) do inc(h);
while (h<t) and compareb(q[h+],q[h]) do inc(h);
b[j]:=f[p,q[h]]+vb[i]*q[h];
end;
h:=;
t:=;
q[]:=m;
for j:=m downto do //卖出情况
begin
if j<>m then
begin
while (h<t) and compares(j,q[t]) do dec(t);
inc(t);
q[t]:=j;
end;
l:=j+ns[i];
if l>m then l:=m;
while (q[h]>l) do inc(h);
while (h<t) and compares(q[h+],q[h]) do inc(h);
s[j]:=f[p,q[h]]+vs[i]*q[h];
end;
for j:= to m do //求总的最大
f[i,j]:=max(f[i-,j],max(b[j]-vb[i]*j,s[j]-vs[i]*j));
end;
ans:=f[n,]; //显然手上无股票最合算
writeln(ans);
end.