若水而净万物

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://iuaaui.blogbus.com/logs/5318015.html

题目一：道路重建(USACO_2002_Feb02 Rebuilding Roads)（PKU1947)(程序附后)

题目大意是给一棵树，要去掉最少的边，使一棵子树从中分离出来，且这棵子树要恰有B个节点。

很容易想到此题为树型Dp,用状态[i,j]来表示以节点i为根，得到一棵j个节点的子树至少要去多少条边（请注
意，这里定义的节点i是这棵子树的根,所以一定包含这棵去掉一些边后所得到的j个节点的子树里面）。怎么
转移呢？如果穷举i的子节点保留还是不保留，如果保留，保留多少个。那么这道题目又退化成完全的搜索了。。不难想到,因为节点i的所有子节点是一个线性结构,我们可以双重Dp!!

下面讲一下第二重的Dp:
对于一个节点i,
设它的儿子依次为1,2,....,x.再设一个状态(k,m)表示到节点i的第k个儿子,要保留m个节点,至少要去掉多少条边.这样,对于这个节点i,我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是选这个k,二是不选这个k,
1.如果不选k,那么(k-1,m)+1--->(k,m)(加1是因为不选这个儿子k,所以k和i所连的边应该断开,那么花费就要加1).
2.如果选nk,那么(k-1,j)+[k,m-j]--->(k,m)(注意,中括号所表示的状态时第一重动规所得到的状态,在这里[k,m-j]的意思就是节点k为根，得到一棵(m-j)个节点的子树至少要去多少条边)

那么就很容易转移了:(k,m)=min{(k-1,j)+[k,m-j]{0<=j<=m},(k-1,m)+1},边界自己想吧。。。。。对于这个节点i,算完所有的(1,m),(2,m),...,(x,m)后,[i,m+1]就等于(x,m)(这里+1是因为i这个节点要保留),每次算出(i,B)后,动态更新下ans就行了...Dp时候的顺序可以记忆化搜索,也可以按后序遍历的顺序进行Dp...

尽管讲了这么多,感觉还是有很多细节问题没有讲清楚,这还是要自己思考一下的,这里只是提供了一个大致的
思路而已...(更多时候，这个思路可能只有作者本人才能看懂的--!)。如果谁有更好的方法,欢迎留言:)

题目二： 贪吃的九头龙（NOI2002_DAY1）
题目大意是给一棵树，再给m种点，这些点要覆盖这棵树的所有节点，且每种种类的点至少要用一次，还规定第一种点必须恰好用K次。这棵树的每一条边都有一个权值（每条边的权值可能不同）。对于某条边，若这条边的两个顶点种类相同，则总权值需要加上这条边的权值。问总权值最少是多少。（可能描述的有些模糊，不懂的看一下原题吧。。。）

首先，要明确一点，就是除了m=2的情况外，如果有的边的两个顶点种类相同，那么这种种类一定是第一种！这能保证解是最优的！发现了这个，就意味着问题解决了一半了。接下来就是状态表示了。。
不难想到用[i,j]表示节点i，恰有j个节点被第一种类的点覆盖，总权值最小是多少。不！这还不够！我们必
须增加一维！这一维不是0就是1，0表示节点i被第一种类的点覆盖，1表示节点i被非第一种类的点覆盖（就是被第二或第三...或第m种类的点覆盖啦--！）。即状态是[i，j，0/1]怎么转移？这不禁联想到上面的第一题，如果还是这样进行一重Dp,那也就是退化成单纯的搜索了。。我们必须进行双重Dp!!

下面还是讲一下第二重的Dp:
还是和上题一样，对于一个节点i，它是0或1类型的。这里只举0类型的例子（即不妨假设节点i被第一种类的点覆盖）。我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是这个儿子类型是0,二是这个儿子的类型是1。
转移就不细讲了。因为涉及到很多很多的细节问题，并且不把这些细节问题讲清楚的话，转移就讲不清楚。而讲清楚这些细节问题至少需要1000+个字。所以就不详细展开讲了。。。。-_-！-_-！-_-!。。。。

总结一下。这两道题都是TreeDp,都是需要双重Dp.可以说,它们两的本质是相同的.可是,不同在哪呢?为什么第二题《贪吃的九头龙》要再加一维呢?深入思考,可以看出它们两的转移方式不同,即option不同.对于第一题,转移的时候是对边而言选还是不选的.对于第二题,转移的时候是对点而言选0类型还是选1类型.而状态是记录在点上,而不是记录在边上.所以第一题只要二维而第二题要三维.换句话说,如果我们表示状态的时候把状态记录在边上,那么第二题只要二维而第一题要三维了。上述的一段话正是本文想要说明的关键部分，有些问题虽然形式不同，但本质相同，所以只有把握本质，深入思考，才能豁然开朗。。。。。

刚搞到一个code_to_html的软件Highlight Code Converter，效果感觉不错：）。故把上述第一题的代码上。

P.S.第二题我写了7KB,很烂,所以不发上来了.

CODE:

{
Author: ShangShanRuoShui
PROG: Rebuilding_Roads
Description: Double_Tree_Dp
}
const
     maxn=200;
var
   ans,n,k,len:longint;
   work:array[0..maxn] of longint;
   g:array[0..maxn,0..maxn] of longint;
   link:array[0..maxn,0..maxn] of longint;
   opt1,opt2:array[0..maxn,0..maxn] of longint;
   v:array[0..maxn] of boolean;
   son,brother,up:array[0..maxn] of longint;
procedure init;
var
   i,a,b:longint;
begin
     readln(n,k);
     for i:=1 to n-1 do
      begin
           readln(a,b);
           g[a,b]:=1;
           g[b,a]:=1;
      end;
end;
procedure build(now:longint);
var
   i:longint;
   chk:boolean;
begin
     v[now]:=true;
     chk:=false;
     for i:=1 to n do
     if (g[now,i]=1)and(not(v[i])) then
      begin
           if not(chk) then
            begin
                 chk:=true;
                 son[now]:=i;
            end;
           inc(link[now,0]);
           link[now,link[now,0]]:=i;
           brother[up[now]]:=i;
           up[now]:=i;
           build(i);
      end;
end;
procedure work1(now:longint);
var
   i:longint;
begin
     for i:=link[now,0] downto 1 do work1(link[now,i]);
     inc(len);
     work[len]:=now;
end;
procedure TreeDp;
var
   i,j,now,min,m:longint;
begin
     for i:=1 to n do
       for j:=0 to k do
      begin
           opt1[i,j]:=maxlongint;
           opt2[i,j]:=maxlongint;
      end;
     for now:=1 to len do
     begin
           if son[work[now]]=0 then opt1[work[now],1]:=0
                               else
           for i:=0 to k-1 do opt1[work[now],i+1]:=opt2[son[work[now]],i];
        if opt1[work[now],k]<>maxlongint then
        begin
           if now=len then
           begin
                if opt1[work[now],k]<ans then ans:=opt1[work[now],k];
           end
           else
           begin
                if opt1[work[now],k]+1<ans then ans:=opt1[work[now],k]+1;
           end;
        end;
         if brother[work[now]]=0 then
                begin
                     opt2[work[now],0]:=1;
                     for j:=1 to k do opt2[work[now],j]:=opt1[work[now],j];
                end
                else
                begin
                     opt2[work[now],0]:=opt2[brother[work[now]],0]+1;
                     for i:=1 to k do
                      if opt2[brother[work[now]],i]<>maxlongint then
                      opt2[work[now],i]:=opt2[brother[work[now]],i]+1;
                     for i:=1 to k do
                  begin
                       min:=opt2[work[now],i];
                       for m:=1 to i do
                          if (opt2[brother[work[now]],i-m]<>maxlongint)and
                             (opt1[work[now],m]<>maxlongint) then
                             begin
                                 if min>opt2[brother[work[now]],i-m]+opt1[work[now],m] then
                                    min:=opt2[brother[work[now]],i-m]+opt1[work[now],m];
                             end;
                       opt2[work[now],i]:=min;
                  end;
                end;
     end;
end;
begin
     ans:=maxlongint;
     fillchar(v,sizeof(v),false);
     init;
     build(1);
     work1(1);
     TreeDp;
     writeln(ans);
end.