NOT A BLOG | sqybi

SGU 104 — Little shop of flowers

Posted on 五月 10th, 2008.

很经典的DP了.
f[i, j]表示前i束花放在前j个花瓶里,其中第i束花必须放在第j个花瓶.转移方程很显然.
似乎没有第i束花必须放在第j个花瓶的条件,转移复杂度会低…
反正随便写写就可以AC啦…

{
SGU 104; Little shop of flowers
- sqybi’s code
- DP
}
//for my winsty
program sgu104_sqybi;
  const
    nn = 100;

  var
    n, m, i, j, p, min: longint;
    a, d, path: array[1..nn, 1..nn]of longint;

  procedure f(x, y: longint);
    var
      i: longint;
    begin
      if x = y then begin
        d[x, y] := 0;
        for i:=1 to x do d[x, y] := d[x, y] + a[i, i];
        exit;
      end;
      if x = 1 then begin
        d[x, y] := a[x, y];
        exit;
      end;
      d[x, y] := - maxlongint;
      for i:=x-1 to y-1 do begin
        if d[x-1, i] = -1 then f(x-1, i);
        if d[x-1, i] > d[x, y] then begin
          d[x, y] := d[x-1, i];
          path[x, y] := i;
        end;
      end;
      d[x, y] := d[x, y] + a[x, y];
    end;

  procedure print(x, y: longint);
    var
      i: longint;
    begin
      if path[x, y] <> 0 then
        print(x-1, path[x, y])
      else begin
        if x = 1 then
          write(y, ‘ ‘)
        else
          for i:=1 to x do
            write(i, ‘ ‘);
        exit;
      end;
      write(y, ‘ ‘);
    end;

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

    fillchar(d, sizeof(d), $FF);
    min := - maxlongint;
    for i:=n to m do begin
      if d[n, i] = -1 then f(n, i);
      if d[n, i] > min then begin
        min := d[n, i];
        p := i;
      end;
    end;
    writeln(min);
    print(n, p);
  end.

阅读(92 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “SGU 104 — Little shop of flowers”

Comments RSS Feed

Where's The Comment Form?