SCOI2010 and SXOI2014 股票交易（DP）

 1 var head,tail,i,n,maxp,w,t,ans,j:longint;
 2     as,bs,ap,bp,q,val:array[0..2020] of longint;
 3     f:array[0..2020,0..2020] of longint;
 4 function max(x,y:longint):longint;
 5  begin
 6  if x>y then exit(x) else exit(y);
 7  end;
 8 procedure init;
 9  begin
10  readln(n,maxp,w);ans:=0;
11  for i:=1 to n do readln(ap[i],bp[i],as[i],bs[i]);
12  end;
13 procedure main;
14  begin
15  fillchar(f,sizeof(f),128);
16  f[0,0]:=0;
17  for i:=1 to n do
18   begin
19    for j:=0 to as[i] do f[i,j]:=-j*ap[i];
20    for j:=0 to as[i] do
21     f[i,j]:=max(f[i,j],f[i-1,j]);
22    t:=i-w-1;
23    if t>=0 then
24     begin
25      head:=0;tail:=0;
26      for j:=0 to maxp do
27       begin
28        while (head<tail) and (q[head]<j-as[i]) do inc(head);
29        while (head<tail) and (f[t,j]+j*ap[i]>=val[tail-1]) do dec(tail);
30        val[tail]:=f[t,j]+j*ap[i];
31        q[tail]:=j;inc(tail);
32        if head<tail then f[i,j]:=max(f[i,j],val[head]-j*ap[i]);
33       end;
34      head:=0;tail:=0;
35      for j:=maxp downto 0 do
36       begin
37        while (head<tail) and (q[head]>j+bs[i]) do inc(head);
38        while (head<tail) and (f[t,j]+j*bp[i]>=val[tail-1]) do dec(tail);
39        val[tail]:=f[t,j]+j*bp[i];
40        q[tail]:=j;inc(tail);
41        if head<tail then f[i,j]:=max(f[i,j],val[head]-j*bp[i]);
42       end;
43      end;
44     ans:=max(ans,f[i,0]);
45    end;
46  writeln(ans);
47  end;
48 begin
49  init;
50  main;
51 end.                                          

 1 type
 2   ji=record
 3   w,s:longint;
 4 end;
 5 var
 6   q:array[0..2005] of ji;
 7   f:array[-2000..2000,0..2000] of longint;
 8   x,i,j,k,head,tail,t,maxp,w,api,bpi,asi,bsi:longint;
 9 
10 function max(x,y:longint):longint;
11 begin
12   if x>y then exit(x);
13   exit(y);
14 end;
15 
16 begin
17   readln(t,maxp,w);
18   for i:=-t to t do
19     for j:=1 to maxp do
20       f[i,j]:=-1000000000;
21   for i:=1 to t do
22     begin
23       readln(api,bpi,asi,bsi);
24       head:=1;
25       tail:=1;
26       f[i]:=f[i-1];
27       q[1].s:=0;
28       q[1].w:=f[i-w-1,0];
29       for j:=1 to maxp do
30         begin
31           inc(tail);
32           q[tail].w:=f[i-w-1,j]+j*api;
33           q[tail].s:=j;
34           while (head<tail)and(q[tail-1].w<q[tail].w) do
35             begin
36               q[tail-1]:=q[tail];
37               dec(tail);
38             end;
39           while (head<=tail)and(q[tail].s<j-asi) do inc(head);
40           f[i,j]:=max(f[i,j],q[head].w-api*j);
41         end;
42       head:=1;
43       tail:=1;
44       q[1].s:=maxp;
45       q[1].w:=f[i-w-1,maxp]+maxp*bpi;
46       for j:=maxp-1 downto 0 do
47         begin
48           inc(tail);
49           q[tail].w:=f[i-w-1,j]+j*bpi;
50           q[tail].s:=j;
51           while (head<=tail)and(q[tail].w<x) do
52             begin
53               q[tail-1]:=q[tail];
54               dec(tail);
55             end;
56           while (head<=tail)and(q[head].s>j+bsi) do inc(head);
57           f[i,j]:=max(f[i,j],q[head].w-j*bpi);
58         end;
59     end;
60   writeln(f[t,0]);
61 end.