naptime.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 58 行

{
PROB:naptime
LANG:PASCAL
}

program naptime;
const
  maxn=3830;
var
  u:array[1..maxn]of longint;
  yes,no{whether Goneril sleeps at 1}:array[boolean{odd(present time)},
           0..maxn-1{how long Goneril has slept},
           boolean{true if Goneril sleeps at the present moment}] of int64;
  n,b,i,j:word;
function min(a,b:word):word;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:int64):int64;
  begin
    if a>b then max:=a else max:=b;
  end;
begin
  assign(input,'naptime.in');reset(input);
  assign(output,'naptime.out');rewrite(output);

  read(n,b);
  for i:=1 to n do
    read(u[i]);
  yes[true,0,false]:=-1;yes[true,0,true]:=-1;
  yes[true,1,false]:=-1;yes[true,1,true]:=0;
  no[true,0,false]:=0;no[true,0,true]:=-1;
  no[true,1,false]:=-1;no[true,1,true]:=-1;
  for i:=2 to n do
    for j:=0 to min(i,b) do begin
      yes[odd(i),j,false]:=max(yes[not odd(i),j,false],yes[not odd(i),j,true]);
      no[odd(i),j,false]:=max(no[not odd(i),j,false],no[not odd(i),j,true]);
      if j=0 then begin
        yes[odd(i),j,true]:=-1;
        no[odd(i),j,true]:=-1;
      end
      else begin
        if yes[not odd(i),j-1,true]<0 then
          yes[odd(i),j,true]:=yes[not odd(i),j-1,false]
        else
          yes[odd(i),j,true]:=max(yes[not odd(i),j-1,false],yes[not odd(i),j-1,true]+u[i]);
        if no[not odd(i),j-1,true]<0 then
          no[odd(i),j,true]:=no[not odd(i),j-1,false]
        else
          no[odd(i),j,true]:=max(no[not odd(i),j-1,false],no[not odd(i),j-1,true]+u[i]);
      end;
    end;
  writeln(max(max(yes[odd(n),b,true]+u[1],yes[odd(n),b,false]),
              max(no[odd(n),b,true],no[odd(n),b,false])));

  close(input);close(output);
end.