zju1346 Comparing Your Heroes [动态规划] 解题报告

jesonpeng 2021-08-17 原文

http://andyzh1314.ycool.com/post.1050670.html

zju1346 Comparing Your Heroes [动态规划] 解题报告

用的动态规划的记忆化方法。

将得到的最优解存在了ans数组里。

程序应用到了位运算，我解释一下：

举个例子：ans[ 3 ]表示将 3 转化成二进制为 11他表示第一个人，和第二个人两人的排列总数。

ans[4] 将4转化成二进制为 100 表示第三个人的排列总数。

order [i] 存的是二进制下形如100……00 {i-1个0 }的数。

采取递归求解：

我们想求一堆人的排列总数，它等于在这一堆人中刨去每一个入度为 0 的人，剩下的人的排列总数的和。具体实现也借助了回溯法。

如果只剩下一个人，那么排列总数为1，这是递归的边界。

PROGRAM p1346;

CONST
Maxn=16;

VAR
        n,total                 :Longint;
        name                    :array[1..maxn]of String;
        ans                     :array[0..65535]of Longint;
        ind,order               :array[1..maxn+1]of Longint;
        whether                 :array[1..maxn,1..maxn]of Boolean;

PROCEDURE MakeOrder;
var
i :Longint;
begin
order[1]:=1;
for i:=2 to maxn+1 do order[i]:=order[i-1] shl 1;
end;

PROCEDURE Readin;
var
i,p,q :Longint;
s :String;

        Function number(t:String):Longint;
        var
                i               :Longint;
        begin
        for i:=1 to total do
                if name[i]=t then
                        begin
                        number:=i;
                        exit;
                        end;
        inc(total);
        name[total]:=t;
        number:=total;
        end;

begin
readln(n);
total:=0;
fillchar(ind,sizeof(ind),0);
fillchar(whether,sizeof(whether),0);

for i:=1 to n do
        begin
        readln(s);
        p:=number(copy(s,1,pos(\’ \’,s)-1));
        q:=number(copy(s,pos(\’ \’,s)+1,length(s)-pos(\’ \’,s)));
        if whether[p][q] then continue;
        whether[p][q]:=true;
        inc(ind[q]);
        end;

while not eof and eoln do readln;

for i:=1 to order[total+1]-1 do ans[i]:=-1;
ans[0]:=1;
end;

FUNCTION Answer(p:Longint):Longint;
var
        i,j                             :Longint;
begin
if ans[p]>=0 then
        begin
        Answer:=ans[p];
        exit;
        end;

ans[p]:=0;
for i:=1 to total do
        if (ind[i]=0) and (p and order[i] = order[i]) then
                begin
                for j:=1 to total do
                        if whether[i][j] then dec(ind[j]);

ans[p]:=ans[p] + Answer(p xor order[i]);

                for j:=1 to total do
                        if whether[i][j] then inc(ind[j]);
                end;

Answer:=ans[p];
end;

BEGIN
makeOrder;
while not eof do
        begin
        Readin;
        writeln(Answer(order[total+1]-1));
        end;
END.