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]<a[j]+a[i] then
          begin
            swap(a[i],a[j]);
          end;
  end;
function tinh(x : string) : longint;
  var i,j : longint;
  begin
    j:= 0;
    for i:=1 to length(x) do
      j := j + ord(x[i])-48;
    exit(j);
  end;
function calc(x,y : longint) : longint;
  var tg : longint;
  begin
    tg:=(x-y) mod 9;
    if tg<0 then tg:=tg+9;
    exit(tg);
  end;
function max2(x,y : string) : string;
  begin
    if length(x)>length(y) then exit(x);
    if lengtH(x)<length(y) then exit(y);
    if 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.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*