明显的单调队列……
但下面的程序一直有bug
附上题解：http://blog.csdn.net/njlcazl/article/details/8611042
附上我的代码：
var head,tail,i,n,maxp,w,t,ans,j:longint;
as,bs,ap,bp,q,val:array[..] of longint;
f:array[..,..] of longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
procedure init;
begin
readln(n,maxp,w);ans:=;
for i:= to n do readln(ap[i],bp[i],as[i],bs[i]);
end;
procedure main;
begin
fillchar(f,sizeof(f),);
f[,]:=;
for i:= to n do
begin
for j:= to as[i] do f[i,j]:=-j*ap[i];
for j:= to as[i] do
f[i,j]:=max(f[i,j],f[i-,j]);
t:=i-w-;
if t>= then
begin
head:=;tail:=;
for j:= to maxp do
begin
while (head<tail) and (q[head]<j-as[i]) do inc(head);
while (head<tail) and (f[t,j]+j*ap[i]>=val[tail-]) do dec(tail);
val[tail]:=f[t,j]+j*ap[i];
q[tail]:=j;inc(tail);
if head<tail then f[i,j]:=max(f[i,j],val[head]-j*ap[i]);
end;
head:=;tail:=;
for j:=maxp downto do
begin
while (head<tail) and (q[head]>j+bs[i]) do inc(head);
while (head<tail) and (f[t,j]+j*bp[i]>=val[tail-]) do dec(tail);
val[tail]:=f[t,j]+j*bp[i];
q[tail]:=j;inc(tail);
if head<tail then f[i,j]:=max(f[i,j],val[head]-j*bp[i]);
end;
end;
ans:=max(ans,f[i,]);
end;
writeln(ans);
end;
begin
init;
main;
end.
还有另一位oier的代码：
type
ji=record
w,s:longint;
end;
var
q:array[..] of ji;
f:array[-..,..] of longint;
x,i,j,k,head,tail,t,maxp,w,api,bpi,asi,bsi:longint; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; begin
readln(t,maxp,w);
for i:=-t to t do
for j:= to maxp do
f[i,j]:=-;
for i:= to t do
begin
readln(api,bpi,asi,bsi);
head:=;
tail:=;
f[i]:=f[i-];
q[].s:=;
q[].w:=f[i-w-,];
for j:= to maxp do
begin
inc(tail);
q[tail].w:=f[i-w-,j]+j*api;
q[tail].s:=j;
while (head<tail)and(q[tail-].w<q[tail].w) do
begin
q[tail-]:=q[tail];
dec(tail);
end;
while (head<=tail)and(q[tail].s<j-asi) do inc(head);
f[i,j]:=max(f[i,j],q[head].w-api*j);
end;
head:=;
tail:=;
q[].s:=maxp;
q[].w:=f[i-w-,maxp]+maxp*bpi;
for j:=maxp- downto do
begin
inc(tail);
q[tail].w:=f[i-w-,j]+j*bpi;
q[tail].s:=j;
while (head<=tail)and(q[tail].w<x) do
begin
q[tail-]:=q[tail];
dec(tail);
end;
while (head<=tail)and(q[head].s>j+bsi) do inc(head);
f[i,j]:=max(f[i,j],q[head].w-j*bpi);
end;
end;
writeln(f[t,]);
end.
这两种代码方法是一样的，但求解的过程不一样，可以挑选自己喜欢的来写。
ps：这两个代码都有bug，在bzoj上都是wa……