FP – SPOJ

Đề bài: http://vn.spoj.com/problems/FP/

Thuật toán:

• Bài này sử dụng phương pháp quy hoạch động. Các bạn có thể đọc code bên dưới để hiểu rõ hơn.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=100;
  oo=trunc(1e9);
  base=9;
var
  f : array[0..maxn,0..maxn,0..10] of string;
  a : array[1..maxn] of string;
  s : array[1..maxn] of longint;
  i,j,n,t,tt,k : longint;
procedure enter;
  begin
    readln(n,k);
    for i:=1 to n do readln(a[i]);
  end;
procedure swap(var x,y : string);
  var tg : string;
  begin
    tg:=x;x:=y;y:=tg
  end;
procedure sort;
  begin
    for i:=1 to n do
      for j:=i+1 to n do
        if a[i]+a[j]length(y) then exit(x);
    if lengtH(x)y then exit(x) else exit(y);
  end;
procedure process;
  var i,j,jj : longint;
  begin
    sort;
    for i:=1 to n do s[i] := tinh(a[i]);
    for i:=0 to n do
      for j:=0 to n do
        for jj:=0 to 10 do
          f[i,j,jj] := '-1';
    for i:=0 to n do f[i,0,0] := '';
    for i:=1 to n do
      for j:=1 to min(k,i) do
        for jj := 0 to 8 do
          begin
            if f[i-1,j,jj]<>'-1' then f[i,j,jj] := f[i-1,j,jj];
            if f[i-1,j-1,calc(jj,s[i])]<>'-1' then
              if f[i,j,jj]<>'-1' then f[i,j,jj] := max2(f[i,j,jj],f[i-1,j-1,calc(jj,s[i])]+a[i]) else f[i,j,jj] := f[i-1,j-1,calc(jj,s[i])]+a[i];
          end;
  end;
procedure print;
  begin
    if f[n,k,0]='' then writeln(-1) else
    writeln(f[n,k,0]);
  end;
begin
  assigN(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(t); k:=9;
  for tt:=1 to t do
  begin
    enter;
    process;
    print;
  end;
end.