tree-dp理解与运用.doc

树型动态规划讲解树型动态规划是动态规划中的一种比较特殊的种类，他的特殊，在于这种动态规划在树这种数据结构上。所以这种动态规划就结合了树的特点。使用递归方式解答。状态总是通过每层来划分的，并且从也节点到根的方向进行状态转移（反过来也可，但不简便）。树再这里有两种分类，一种是有根树，一种是无根树。在一棵树中，一旦根确定，就意味着这颗树的结构也就确定了。所以有根树比无根树相对简单一些。无根树分为两种情况，依题目而异。有些题目中，答案是和树的形态没有关系的，此时我们只需要随机选取一个节点作为根建树即可。还有些题目，答案和树的形态有关系，此时我们必须要枚举每个节点作为跟的情况进行建树，求解，才可以得到答案。Ural 1018二叉苹果树（有根树,二叉树dp）题目有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1（从这个条件可以判断这个树是有根树）。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 / 3 4 / 1现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。输入格式第1行2个数，N和Q(1=Q= N,1N=100)。N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。输出格式一个数，最多能留住的苹果的数量。样例输入5 21 3 11 4 102 3 203 5 20样例输出21题目地址：http:/acm.timus.ru/submit.aspx?space=1&num=1039解析：因为题目一给出就是二叉的，所以很容易就可以写出方程：a(I,j):=max(a(i.left,k)+a(i.right,j-k),0=k0 then for i:=1 to q do for j:=0 to i-1 do begin t:=dpx,1+dpc1,j+dpc2,i-1-j; if tdpx,i then dpx,i:=t; end; end;begin read(n,q);inc(q); for i:=1 to n-1 do read(v1i,v2i,applei); dfs(1); writeln(dp1,q);end.Ural 1039 没有上司的晚会（普通树，有根树DP）背景有个公司要举行一场晚会。为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司（上司的上司，上司的上司的上司都可以邀请）。题目每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。输入格式第1行一个整数N（1=N=6000）表示公司的人数。接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128=xb then max:=a else max:=b; end;procedure dfs(v:word); begin while nowv0 do begin dfs(childnowv); inc(yesv,nochildnowv); inc(nov,max(yeschildnowv,nochildnowv); nowv:=prenowv; end; end;begin read(n); for i:=1 to n do read(yesi); fillchar(pres,sizeof(pres),1); root:=n*(n+1) div 2; for i:=1 to n-1 do begin read(x,y); childi:=x; prei:=nowy; nowy:=i; if presx then begin dec(root,x); presx:=false; end; end; dfs(root); writeln(max(yesroot,noroot);end.战略游戏(普通树，无根树DP，形态无关)ProblemBob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵.Input第一行为一整数，表示有组测试数据每组测试数据表示一棵树，描述如下：第一行 N，表示树中结点的数目。第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)。接下来k个数，分别是每条边的另一个结点标号r1，r2，.，rk。 对于一个n(0n=1500)个结点的树，结点标号在0到n-1之间，在输入数据中每条边只出现一次。 Output输出文件仅包含一个数，为所求的最少的士兵数目。 例如，对于如下图所示的树： 答案为1（只要一个士兵在结点1上）。 Sample Input240 1 11 2 2 32 03 053 3 1 4 21 1 02 00 04 0Sample Output12这道题目是一个经典的问题，来源于同济大学的OJ。是一颗无根树的题目，而且结果和树的形态没有关系分析可见,对于当前结点i,它有num个子结点,它有它有3种状态:1:在当前位放置守卫的情况(被自己所控制)2:不在当前位放置守卫,但是它已经被它的子结点所控制3:不在当前位放置守卫,它还没有被它的子结点所影响(即被其父结点控制)用fi,x表示结点i的第x种情况:1情况的值由其子结点的1,2,3情况得到最优2情况的值由其子结点的1,2情况得到最优3情况的值只可由其2情况求和.第2种情况要特别注意,要求它的子结点中必须有一个是1状况的,所以可以先将最小值求和,然后加上这num个子结点中每个的1情况与最优情况的f值之差-most方程:fi,1:=(minfsonj,1,fsonj,2,fsonj,3)+aifi,2:=(minfsonj,1,fsonj,2)+mostfi,3:=(fsonj,2), 1=j=num还有要注意的一点就是对于极限数据,树被拉成了一条链.有向图解法如果每次递归都开一个数组那么内存会爆,对此,可以不用数组记录子结点,而直接用链表就可以大大节约空间了.甚至把数组改成全局变量也是可行的,就是注意递归调用要在DP之前.代码#include #define MAXN 1501#define MAXINT 2000000000typedef struct int v, num; int childMAXN;node;node aMAXN;int fMAXN4;int min2(int x, int y) return xy?x:y;int min3(int x, int y, int z) return min2(x, min2(y, z);void dp(int i) int j, k,a2; if (ai.num = 0) fi1 = ai.v; fi2 = ai.v; return; fi2 = ai.v; for (j = 1; j = ai.num; j+) dp(ai.childj); fi2 += min3(fai.childj1, fai.childj2, fai.childj3); fi3 += fai.childj1; fi1 = MAXINT; for (j = 1; j = ai.num; j+) a2 = fai.childj2; for (k = 1; k = ai.num; k+) if (j != k) if (aai.childk.num != 0) a2 += min2(fai.childk2, fai.childk1); else a2 += fai.childk2; if (a2 fi1) fi1 = a2; int main() int i, j, m, n, p, r, root; m = MAXINT; r = 0; root = 0; scanf(%d, &n); for (i = 1; i = n; i+) scanf(%d, &p); scanf(%d%d, &ap.v, &ap.num); r += p; for (j = 1; j fs2fs3fsn，则我们让root在每个单位时间内依次通知s1,s2,s3.sn,得到的结果是最优的。也就是froot=maxfsi+i.也就是说哪个儿子的f值最大我们先通知谁。这个是看起来很显然的结论。但是我们需要证明它。简略证明如下：假设root的儿子为s1,s2,s3,sn,且fs1fs2fs3fsn.则我们要证明：froot=maxfsi+i是最优的。我们把通知儿子的次序中任意交换两个。即原来有 ifsj.，通知这两颗子树的最短时间是 minfsi+i,fsj+j；当交换顺序以后，则通知这两个子树的最短时间是Minfsi+j,fsj+i,因为 fsifsj 且 ji, 则我们交换顺序后的到的最小值显然不会比原来的最优值更优。因此算法得到证明。由此得到了我们的主算法：枚举每个节点当作树根，建立无根树。每次进行一次树形动态规划，方程为fi=maxfsj+j 其中sj是i的儿子。这个题目的特点就是最优值和树的形态是有关系的，而这个树是一个无根树，所以需要去枚举节点作为树根的情况才可以确定最优解。#include #include #include #include using namespace std;const int maxn=1024;int resmaxn;struct edge int y; edge* next; edge(int y,edge* next): y(y),next(next)*Emaxn;int root;int parmaxn;int ordermaxn;int costmaxn;int best;int N;void input() scanf(%d,&N); memset(E,0,sizeof(E); for(int i=2;inext) int y=e-y; if(y=parx)continue; pary=x; ordertail+=y; if(head=tail)break; int compare(const void* a,const void* b) return *(int*)a-*(int*)b;int childmaxn;void handle(int x) int childn=0; for(edge* e=Ex;e;e=e-next) int y=e-y; if(y=parx)continue; childchildn+=costy; qsort(child,childn,sizeof(int),compare); costx=0; for(int i=0;icostx) costx=cur; int solve(int x) root=x; bfs(); for(int i=N-1;i=0;-i) handle(orderi); if(costorderibest) return INT_MAX; return costroot;void solve() best=INT_MAX; for(int i=1;i=N;+i) root=i; resi=solve(i); if(resibest) best=resi; void output() printf(%dn,best+1); bool first=true; for(int i=1;i=N;+i) if(resi=best) if(first) first=false; else putchar( ); printf(%d,i); putchar(n);int main() freopen(badnews.in,r,stdin); freopen(badnews.out,w,stdout); input(); solve(); output();Tree-dp技巧：多叉树转二叉树选课 问题描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？输入：第一行有两个整数N,M用空格隔开。(1=N=200,1=M=150)接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1=ki=N, 1=si=0 then exit; treedp(ax.r,y);只有右子树的情况 j:=bax.r,y; for k:=1 to y do左右子树都有的情况 begin treedp(ax.l,k-1); treedp(ax.r,y-k); i:=bax.l,k-1+bax.r,y-k+ax.k; if ij then j:=i; end; bx,y:=j; end;beginreadln(s);assign(input,s);reset(input);readln(n,m);fillchar(f,sizeof(f),0);for i:=0 to n do begin ai.l:=-1;ai.r:=-1;ai.k:=-1;end;build treefor i:=1 to n do begin readln(k,l); ai.k:=l; if fk=0 then ak.l:=i else afk.r:=i; fk:=i; end;bianjiefor i:=-1 to n do for j:=-1 to m do if (i=-1) or (j=0) then bi,j:=0 else bi,j:=-1;tree dptreedp(a0.l,m);outputwriteln(ba0.l,m);end.Tree-dp与其他算法的结合pku1947（DP+背包）Rebuilding RoadsDescriptionThe cows have reconstructed Farmer Johns farm, with its N barns (1 = N = 150, number 1.N) after the terrible earthquake last May. The cows didnt have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree. Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 = P = N) barns from the rest of the barns.Input* Line 1: Two integers, N and P * Lines 2.N: N-1 lines, each with two integers I and J. Node I is node Js parent in the tree of roads. OutputA single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated. Sample Input11 61 21 31 41 52 62 72 84 94 104 11Sample Output2HintA subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed. SourceUSACO 2002 February题目大意：题目大意是给一棵树，要去掉最少的边，使一棵子树从中分离出来，且这棵子树要恰有B个节点。fx，i(1 = i = p)表示以x为根的子树，变成剩下i个点的子树，且剩余子树包含根结点，需要去掉的最少边数。那么父结点的f值可以由它所有的儿子的f值做背包得到。最后的答案是min(min(fi，p) + 1 (2 = i b then exit(b); exit(a);end;procedure init;begin readln(n,p); for i:=1 to n-1 do begin readln(t1,t2); inc(ct1);inc(ct2); mapt1,ct1:=t2; mapt2,ct2:=t1; end; fillchar(used,sizeof(used),false); for i:=1 to n do for j:=0 to n do fi,j:=maxint;end;procedure dfs(now,father:integer);var i,j,k:longint;begin usednow:=true; for i:=1 to cnow do if (mapnow,ifather) and (not(usedmapnow,i) then dfs(mapnow,i,now); fnow,1:=cnow; for i:=1 to cnow do for k:=p-1 downto 0 do if fnow,kmaxint then for j:=1 to p do if fmapnow,i,jmaxint then fnow,k+j:=min(fnow,k+j,(fmapnow,i,j+fnow,k-2);end;procedure print;begin ans:=maxint; for i:=2 to n do ans:=min(ans,fi,p); ans:=min(ans,f1,p); writeln(ans);end;begin init; dfs(1,0); print;end.加分二叉树（二叉树DP，也可理解为类石子合并的线性结构）【问题描述】 设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分 subtree的右子树的加分subtree的根的分数 若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。要求输出； （1）tree的最高加分 （2）tree的前序遍历【输入格式】 第1行：一个整数n（n30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。【输出格式】 第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。【输入样例】 5 5 7 1 2 10【输出样例】 145 3 1 2 4 5valuei,j表示从节点i到节点j所组成的二叉树的最大加分，则动态方程可以表示如下：valuei,j=maxvaluei,i+valuei+1,j,valuei+1,i+1+valuei,i*valuei+2,j, valuei+2,i+2+valuei,i+1*valuei+3,j,valuej-1,j-1+valuei,j-2*valuej,j, valuej,j+valuei,j-1题目还要求输出最大加分树的前序遍历序列，因此必须在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点，用数组rooti,j表示PASCAL源程序$N+program NOIP2003_3_Tree; const maxn=30; var i,j,n,d:byte; a:array1.maxnof byte; value:array1.maxn,1.maxnof comp; root:array1.maxn,1.maxnof byte; s,temp:comp; f1,f2:text;fn1,fn2,fileNo:string; procedure preorder(p1,p2:byte);按前序遍历输出最大加分二叉树 begin if p2=p1 then begin write(f2,rootp1,p2, ); preorder(p1,rootp1,p2-1); preorder(rootp1,p2+1,p2); end; end; begin write(Input fileNo:);readln(fileNo); fn1:=tree.in+fileNo;fn2:=tree.ou+fileNo; assign(f1,fn1);reset(f1); assign(f2,fn2);rewrite(f2); readln(f1,n); for i:=1 to n do read(f1,ai); close(f1); fillchar(value,sizeof(value),0); for i:=1 to n do begin valuei,i:=ai;计算单个节点构成的二叉树的加分 rooti,i:=i;记录单个节点构成的二叉树的根节点 end; for i:=1 to n-1 do begin valuei,i+1:=ai+ai+1;计算相邻两个节点构成的二叉树的最大加分 rooti,i+1:=i;记录相邻两个节点构成的二叉树的根节点；需要说明的是，两个节点构成的二叉树，其根节点可以是其中的任何一个；这里选编号小的为根节点，则编号大的为其右子树；若选编号大的为根节点，则编号小的为其左子树；因此，最后输出的前序遍历结果会有部分不同，但同样是正确的。如果最大加分二叉树的所有节点的度数都是0或2，则最后输出的前序遍历结果是唯一的。 end; for d:=2 to n-1 do begin依次计算间距为d的两个节点构成的二叉树的最大加分 for i:=1 to n-d do begin s:=valuei,i+valuei+1,i+d;计算以i为根节点，以i+1至i+d间所有节点为右子树的二叉树的最大加分 rooti,i+d:=i; 记录根节点i for j:=1 to d do begin temp:=valuei+j,i+j+valuei,i+j-1*valuei+j+1,i+d;计算以i+j为根节点，以i至i+j-1间所有节点为左子树，以i+j+1至i+d间所有节点为右子树的二叉树的最大加分 if temps then begin如果此值为最大 s:=temp;rooti,i+d:=i+j;记下新的最大值和新的根节点 end; end; temp:=valuei,i+d-1+valuei+d,i+d;计算以i+d为根节点，以i至i+d-1间所有节点为左子树的二叉树的最大加分 if temps then begin s:=temp;rooti,i+d:=i+d+1; end; va