战略游戏树形DP

题意/Description：

　　Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

　　请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。

读入/Input：

　输入文件中数据表示一棵树，描述如下：
　　第一行 N，表示树中结点的数目。
　　第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。
　　对于一个n(0 < n <= 1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。

输出/Output：

　输出文件仅包含一个数，为所求的最少的士兵数目。
　　例如，对于如右图所示的树：
　　答案为1（只要一个士兵在结点1上）。

题解/solution：

　这题显然是一道树型DP，不但要考虑子节点对他的根节点的影响，而且每放一个士兵，士兵所在位置既影响他的子节点也影响了他的根节点，状态不难表现出来。

我在做的时候，WA了几次。主要是n是从0开始的，大家在循环是要注意一下，否则会忽略‘0’这个结点。

代码/Code：

<strong>var
  n:longint;
  g:array [0..1501,0..1501] of boolean;
  v,f:array [0..1501] of boolean;
function hh(x:longint):boolean;
var
  i:longint;
begin
  for i:=0 to n-1 do
    if (x<>i) and (g[x,i]) then exit(false);
  exit(true);
end;

function tree(t:longint):longint;
var
  i,j,k,l:longint;
begin
  j:=0; k:=0; l:=0;
  for i:=0 to n-1 do
    if (i<>t) and (g[t,i]) then
      if hh(i) then inc(j) else
        begin
          l:=l+tree(i);
          if not v[i] then inc(k);
        end;
  if (j>0) or (k>0) then
    begin
      v[t]:=true;
      exit(l+1);
    end else exit(l);
end;

procedure main;
var
  i,j,k,l,r,ri:longint;
begin
  read(n);
  for j:=0 to n-1 do
    begin
      read(k,l);
      for r:=1 to l do
        begin
          read(ri);
          g[k,ri]:=true;
          f[ri]:=true;
        end;
    end;
  for j:=0 to n-1 do
    if (f[j]=false) then break;
  if hh(j) then write('1')
           else write(tree(j));
end;

begin
  main;
end.
</strong>

战略游戏 树形DP

战略游戏树形DP