loco.txt

背包类问题浅析和一些背包类问题的解答源程序。

program zx;
var n,m,i,j:integer;
    a:array [1..5500] of 0..100;
    b:array [1..5500] of longint;
    f:array [0..5500,0..3] of longint;

procedure int;
  begin
    readln(n);
    for i:=1 to n do read(a[i]);
    readln;
    read(m);
  end;

procedure dp;
  begin
    fillchar(f,sizeof(f),0);
    fillchar(b,sizeof(b),0);

    for i:=m to n do
      for j:=1 to m do
        b[i]:=b[i]+a[i-j+1];

    for i:=1 to 3 do f[1,i]:=a[1];

    for i:=2 to n do
     for j:=1 to 3 do
       begin
         f[i,j]:=f[i-1,j];
         if (i>=m)and(f[i,j]<f[i-m,j-1]+b[i]) then
           f[i,j]:=f[i-m,j-1]+b[i];
       end;
  end;

BEGIN
  int;
  dp;
  write(f[n,3]);
END.