MAUGIAO - The problem for kid

Tác giả: ladpro98

Ngôn ngữ: Pascal

program maugiao;
uses    math;
const   maxn=20;
        maxV=1 shl maxn;
        fi='';
var     a:array[0..maxn,0..maxn] of longint;
        f:array[-1..maxV] of longint;
        way:array[0..maxV] of int64;
        n,m:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                for j:=1 to n do read(inp,a[i,j]);
                readln(inp);
        end;
        close(inp);
end;

function getbit(i,j:longint):boolean;
begin
        exit((i shr (j-1) and 1)=1);
end;

procedure dp;
var     i,j,t,p:longint;
begin
        way[0]:=1;
        for j:=1 to 1 shl n - 1 do
        begin
                t:=0;
                for i:=1 to n do
                if getbit(j,i) then inc(t);
                for i:=1 to n do
                if getbit(j,i) then
                begin
                        p:=f[j-1 shl (i-1)]+a[t,i];
                        if f[j]<p then
                        begin
                                f[j]:=p;
                                way[j]:=way[j-1 shl (i-1)];
                        end
                        else
                        if f[j]=p then way[j]:=way[j]+way[j-1 shl (i-1)];
                end;
        end;
end;

begin
        input;
        dp;
        write(f[1 shl n-1],' ',way[1 shl n -1]);
end.

Download