题解 P2016 【战略游戏】

难上加兰 · 2015-10-27 19:36:46 · 题解

思路：

树形DP，思路简单

①m不放，f[m,0]=f[m的儿子,1];

②m放，f[m,0]=min(f[m的儿子,1],f[m的儿子,0]);

初始化时，f[x,0]:=0;f[x,1]:=1;

var
  v:array[0..2000]of boolean;
  f:array[0..2000,0..1]of integer;
  c:array[0..2000,0..2000]of integer;
  i,j,k,m,n,r,a:integer;
function min(x,y:integer):integer;
begin
  if x>y then exit(y)
    else exit(x);
end;

function tree(m:integer):integer;
var
  i:integer;
begin
  f[m,0]:=0;
  f[m,1]:=1;//初始化
  for i:=1 to c[m,0]do
    tree(c[m,i]);
  for i:=1 to c[m,0]do
    begin
      inc(f[m,0],f[c[m,i],1]);
      inc(f[m,1],min(f[c[m,i],1],f[c[m,i],0]));
    end;
  if (f[m,0]<>0)and(f[m,1]=0)then
    exit(f[m,0]);
  if (f[m,1]<>0)and(f[m,0]=0)then
    exit(f[m,1]);
  exit(min(f[m,0],f[m,1]));
end;
begin
  fillchar(f,sizeof(f),255);
  fillchar(v,sizeof(v),true);
  readln(n);
  for i:=1 to n do
    begin
      read(m);
      read(c[m,0]);
      for j:=1 to c[m,0]do
        begin
          read(c[m,j]);
          v[c[m,j]]:=false;
        end;
    end;
  for i:=0 to n-1 do
    if v[i] then
      begin
        r:=i;
        break;
      end;
  writeln(tree(r));//输出以根节点为根的最小兵力值
end.