树形DP之个人整理总结

树形DP 第页 Auther:陈江勇2008年10月22日树形DP二叉苹果树(ural1108)题目意思：有一棵苹果树，苹果树的是一棵二叉树，共N个节点，树节点编号为1~N，编号为1的节点为树根，边可理解为树的分枝，每个分支都长着若干个苹果，现在要要求减去若干个分支，保留M个分支，要求这M个分支的苹果数量最多。输入：NM接下来的N-1行是树的边，和该边的苹果数NandM(1≤M<N;1<N≤100)输出：剩余苹果的最大数量。input52131141023203520output21算法：删除了某个分支，那么这个分支下的子分支也同时删除。保留M个分支，也就是删除N-M-1个分支。剩余的最多苹果数=总苹果数-剪掉的苹果数。注意本题给的边并没有按照树根--树叶的形式来给，也没有按照树的顺序给出边。本来想一个节点对应一个分支长着的苹果数量，cost[v]就表示v这个节点的苹果数，可以这样做，但是在输入的时候，不知道这个苹果数量是那个节点的，因为不知道哪个是哪个的子结点。所以用了无向图和苹果数加到边上去。我的解法中：这题的树状DP的整体思想个pku3345是一样的。有一些不一样的地方要注意一下：本程序其实不仅仅针对二叉树，可以是任意的树，删除任意个分支都有算。#include<iostream>#include<vector>#include<limits>usingnamespacestd;#defineMN110intf[2*MN],p[MN],tmp[MN];intN,M;boolvisit[MN];structNODE{ intval; intcost;};vector<NODE>G[MN];inlineintmax(inta,intb){ returna>b?a:b;}inlineintmin(inta,intb){ returna<b?a:b;}voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); } memset(visit,false,sizeof(visit));}intDP(intv,intfrom){ visit[v]=true; inti,j,k,s,w,last,now; s=G[v].size(); if(s==1)//这边不再是s==0 { p[0]=0; return1; } last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i].val; if(visit[w]==true) continue; now=DP(w,from+last+1); p[now]=p[now-1]+G[v][i].cost;//这边不要漏,把节点w也给删除 for(j=0;j<=last+now;j++) tmp[j]=INT_MAX; for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { tmp[j+k]=min(tmp[j+k],f[from+j]+p[k]); } } last+=now; for(j=0;j<=last;j++) { f[from+j]=tmp[j]; } } for(i=0;i<=last;i++) p[i]=f[i+from]; last++;//加上自身节点 returnlast;}intmain(){ inti,a,b,sum,c; NODEtmp; while(scanf("%d%d",&N,&M)!=EOF) { sum=0; my_clear(); for(i=1;i<N;i++) { scanf("%d%d%d",&a,&b,&c); tmp.cost=c; tmp.val=b; G[a].push_back(tmp); tmp.val=a; G[b].push_back(tmp); sum+=c; } DP(1,0); printf("%d\n",sum-f[N-M-1]); } return0;}有限电视网络（pku1155TELE）题目描述：有一个电视台要用电视网络转播节目。这种电视网络是一树，树的节点为中转站或者用户。树节点的编号为1~N,其中1为总站，2~(N-M)为中转站，（总站和中转站统称为转发站）N-M+1~N为用户，电视节目从一个地方传到另一个地方都要费用，同时每一个用户愿意出相应的钱来付电视节目。现在的问题是，在电视台不亏本的前提下，要你求最多允许有多少个用户可以看到电视节目。输入：NMN表示转发站和用户总数，M为用户数以下N-M行，第i行第一个K，表示转发站i和K个（转发站或用户）相连,其后第j对数val,cost表示，第i个转发站到val有边，费用cost.最后一行M个数表示每个用户愿意负的钱。输出：不亏本前提下，可以收到节目最多的用户数。（如果某个用户要收到节目（叶子结点），那么电视台到该用户的路径节点的费用都要付）SampleInput963223293242523627282433311SampleOutput5算法：这是一道树状态DP.状态f(n,k)表示第n个节点发送给k个用户最多能盈利多少，k不超过n所管辖的叶节点个数。那么答案就是使f(root,k)>=0最大的k了。通常我们状态转移的时候是枚举每个子状态的，但是这里我们还得用一个DP来枚举子状态。假设一个节点i有n个子节点，那么求f(i,k)时就要考虑怎么把k分到n个节点上使得盈利最大。下面关键是如何去枚举：如果节点i有X个子结点设为1~~X，假如当前DP算到第j（0=<j<=X）个节点,第j个节点有now个用户,而0~j-1共有last用户，f[i][k]=max(f[i][k],f[i][a]+f[j][b])(其中a+b=k,0=<k<=last+now);f[i][a]表示把a个用户分配给0~~j-1节点，分配b个用户给j这个节点。本程序用写了另外一个用滚动数组来省空间的方法，注意多了一个参数from,否则原来的值会被覆盖掉。#include<iostream>#include<limits>#include<vector>usingnamespacestd;intN,M;vector<int>G[3001];intmoney[3001],cost[3001],p[3001],f[6001],tmp[3001];voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); }}intDP(intv,intfrom){ inti,s,last,now,k,j,w; s=G[v].size(); if(!s) { p[0]=0; p[1]=money[v-N+M]; return1; } last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i]; now=DP(w,from+last+1); for(j=0;j<=last+now;j++) { tmp[j]=INT_MIN; } for(j=1;j<=now;j++) { p[j]-=cost[w]; } for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { if(f[from+j]+p[k]>tmp[j+k]) { tmp[j+k]=f[from+j]+p[k]; } } } tmp[0]=0; last+=now; for(j=0;j<=last;j++) { f[j+from]=tmp[j]; } }/* printf("%d\n",v); for(i=0;i<=last;i++) { printf("%d%d\n",i,f[i+from]); }*/ for(j=0;j<=last;j++) p[j]=f[j+from]; returnlast;}intmain(){ inti,K,j,b; scanf("%d%d",&N,&M); my_clear(); for(i=1;i<=N-M;i++) { scanf("%d",&K); for(j=0;j<K;j++) { scanf("%d",&b); scanf("%d",&cost[b]); G[i].push_back(b); } } for(i=1;i<=M;i++) scanf("%d",&money[i]); DP(1,0); for(i=M;i>=0;i--) { if(f[i]>=0) break; } printf("%d\n",i); return0;}最少步数摘最多的苹果(pku2486AppleTree)DescriptionWshxztisalovelygirl.Shelikesappleverymuch.OnedayHXtakeshertoanappletree.ThereareNnodesinthetree.Eachnodehasanamountofapples.Wshxztstartsherhappytripatonenode.Shecaneatupalltheapplesinthenodesshereaches.HXisakindguy.Heknowsthateatingtoomanycanmakethelovelygirlbecomefat.Sohedoesn’tallowWshxzttogomorethanKstepsinthetree.Itcostsonestepwhenshegoesfromonenodetoanotheradjacentnode.Wshxztlikesappleverymuch.Soshewantstoeatasmanyasshecan.CanyoutellhowmanyapplesshecaneatinatmostKsteps.InputThereareseveraltestcasesintheinputEachtestcasecontainsthreeparts.ThefirstpartistwonumbersNK,whosemeaningswehavetalkedaboutjustnow.Wedenotethenodesby12...N.Sinceitisatree,eachnodecanreachanyotherinonlyoneroute.(1<=N<=100,0<=K<=200)ThesecondpartcontainsNintegers(Allintegersarenonnegativeandnotbiggerthan1000).TheithnumberistheamountofapplesinNodei.ThethirdpartcontainsN-1line.TherearetwonumbersA,Bineachline,meaningthatNodeAandNodeBareadjacent.Inputwillbeendedbytheendoffile.Note:WshxztstartsatNode1.OutputForeachtestcase,outputthemaximalnumbersofapplesWshxztcaneatataline.SampleInput2101112320121213SampleOutput112f[i][j][0]保存对于节点i向其子树走j步(可能有点重复)摘到的最多苹果数f[i][j][1]保存对于节点i向其子树走j步并且返回到i节点摘到的最多苹果数对于叶节点f[i][0][0/1]=apNum[i];对于其它节点f[i][j][0]=max{j-2*p-1步，其中p个子树返回,1个子树不需要返回,所得到最多苹果数,p不定}；f[i][j][1]=max{j-2*p步，p个子树都返回,所得到的最多苹果数,p不定}这两步中间过程都需要DP复杂度=j*子树个数(<n)那么最终结果就是f[1][k][0]整个大的DP时间复杂度<n*(k*n)<2*10^6树型DP中套小DP*/#include<iostream>#include<vector>usingnamespacestd;#defineMN101intback[201][201],go[201][201],num[101],t1[201],t2[201];vector<int>G[MN];intN,K;inlineintmax(inta,intb){ returna>b?a:b;}voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); } memset(go,0,sizeof(go)); memset(back,0,sizeof(back));}voidDP(intv,intp){ inti,s,w,j,m,n; s=G[v].size(); for(i=0;i<s;i++) { w=G[v][i]; if(w==p) continue; DP(w,v); back[w][0]=0; back[w][1]=0; go[w][0]=0; for(j=K;j>=2;j--) { back[w][j]=back[w][j-2]+num[w]; } for(j=K;j>=1;j--) { go[w][j]=go[w][j-1]+num[w]; } memset(t1,0,sizeof(t1)); memset(t2,0,sizeof(t2)); for(m=0;m<=K;m++) { for(n=0;n<=m;n++) { t1[m]=max(t1[m],back[v][n]+back[w][m-n]); t2[m]=max(t2[m],max(go[v][n]+back[w][m-n],back[v][n]+go[w][m-n])); } } for(j=0;j<=K;j++) { back[v][j]=t1[j]; go[v][j]=t2[j]; } }}intmain(){ inta,b; while(scanf("%d%d",&N,&K)!=EOF) { inti; for(i=1;i<=N;i++) scanf("%d",&num[i]); my_clear(); for(i=1;i<N;i++) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } DP(1,0); intans=max(go[1][K],back[1][K]); ans+=num[1]; printf("%d\n",ans); } return0;}钻石总统(pku3345BribingFIPA)题目大意：有个人要竞选某职务,有N个国家参选，他想通过贿赂某些国家来赢得这个国家的选票，每个国家都要花费相应的钻石才可以被贿赂。因为国家与国家之间存在着控制关系，付费给某个国家，那么就可以赢得这个国家和它直接或间接控制的所有国家的选票。其实国家的控制关系可以看成一棵树，对于本题，是给一个森林。你的任务是如果至少要赢得M个国家的选票，最少要花多少钻石。输入：32//N,M接下来是N行，每行前两个为国家名和贿赂改国家需要的钻石数，后面跟着的是这个国家可以控制的国家名字，可以没有。Aland10Boland20AlandColand15#输出：最后需要的钻石数。输入处理用了sstream，真的很好用。不然可能很不好处理。这题要注意：输入不会有环。但是给你的数可能不联通，所以加一个根节点吧所有的树都连成一棵树，然后在书上进行DP.DP的方法和1155的方法类似，也用了from参数。#include<iostream>#include<vector>#include<map>#include<limits>#include<sstream>usingnamespacestd;map<string,int>mp;#defineMN210vector<int>G[MN];intf[2*MN],p[MN],tmp[MN],cost[MN],in[MN];intN,M;charchartmp[1000];inlineintmax(inta,intb){ returna>b?a:b;}inlineintmin(inta,intb){ returna<b?a:b;}voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); } memset(in,0,sizeof(in)); mp.clear();}intDP(intv,intfrom){ inti,j,k,s,w,last,now; s=G[v].size(); if(s==0) { p[0]=0; p[1]=cost[v]; return1; } last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i]; now=DP(w,from+last+1); for(j=0;j<=last+now;j++) tmp[j]=INT_MAX; for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { tmp[j+k]=min(tmp[j+k],f[from+j]+p[k]); } } last+=now; for(j=0;j<=last;j++) { f[from+j]=tmp[j]; } } f[from+last+1]=cost[v]; last++; for(i=0;i<=last;i++) p[i]=f[i+from]; returnlast;}intmain(){ inti,root,a,b,id; stringt; while(gets(chartmp)) { if(chartmp[0]==0) continue; if(chartmp[0]=='#') break; stringstreamss(chartmp); ss>>N>>M; id=1; my_clear(); for(i=1;i<=N;i++) { scanf("%s",chartmp); if((a=mp[chartmp])==0) { a=mp[chartmp]=id++; } scanf("%d",&cost[a]); gets(chartmp); stringstreamss(chartmp); while(ss>>t) { if((b=mp[t])==0) { b=mp[t]=id++; } in[b]++;// G[a].push_back(b);//这两个是放在if外，开始的时候错了 } } for(i=1;i<=N;i++) { if(in[i]==0) { G[0].push_back(i); } } cost[0]=0; inttt=DP(0,0); intans=INT_MAX; for(i=M;i<=N;i++) { if(ans>f[i]) { ans=f[i]; } } printf("%d\n",ans); } return0;}删除最少的边使得树剩下的给定数目节点(pku1947RebuildingRoads)题目的意思：给你一棵树，求通过求通过删除最少的边，使得剩余子树有给定的节点数。输入：N,P//N为节点总数，P为删除边后剩余的节点树以下N-1行给出树的边。题目没说清楚给出的边是否是有向的。对于本题可以按照有向树来做，其实无向树来做更保险，应用性更广。看成有向树，对于本题树根就是1，题目没说，判断一下更保险，如果是看成无向树，则无所谓谁为根节点。开始的时候，对于本题一直按照以往的树形DP的方法来做，一直错。查了好久才查出哪里错了，因为看到别人的程序的一个地方，多了一段程序，删除这一部分则是错误的。ans=f[root][p];for(i=1;i<=n;i++)//这个for循环是必须的。{if(f[i][p]<ans)ans=f[i][p]+1;//这边之所以要加一因为要删除i节点和其父亲节点的连接}后来我就在DP的函数末尾，多了一个判断。按照以往的DP方法，一下这个例子是错的，输出的是3，而答案是11271111121223244548565789810如果看成有向树,1为根，以1为根进行DP的最后的答案是3，原因是这样DP的所有结果(即剩余的P个节点)都包含根节点1,而对于上面一个数据，一最后的节点不包含根根节点，而是删除一个边后，边下面的子树保留，上面的部分（包括根节点全部删除），所以就多了判断那一部分。即在DP的子问题中判断是否有更优解。#include<iostream>#include<vector>usingnamespacestd;#defineMN160vector<int>G[MN];intf[2*MN],p[MN],tmp[MN],N,P,in[MN],root;intans;voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); }}inlineintmin(inta,intb){ returna<b?a:b;}intDP(intv,intfrom){ intlast,now,w,i,s,j,k; s=G[v].size(); last=0; f[from]=0; for(i=0;i<s;i++) { w=G[v][i]; now=DP(w,last+from+1); for(j=0;j<=last+now;j++) { tmp[j]=INT_MAX; } for(j=0;j<=last;j++) { for(k=0;k<=now;k++) { tmp[j+k]=min(tmp[j+k],f[j+from]+p[k]); } } last+=now; for(j=0;j<=last;j++) { f[j+from]=tmp[j]; } } p[0]=0; for(j=0;j<=last;j++) p[j]=f[j+from]; last++; p[last]=0; if(last>=P&&v!=root&&p[last-P]+1<ans) { ans=p[last-P]+1; } p[last]=1; returnlast;}intmain(){ inti,a,b; while(scanf("%d%d",&N,&P)!=EOF) { my_clear(); ans=INT_MAX; memset(in,0,sizeof(in)); for(i=1;i<N;i++) {//对于本题可以按照有向树来做，其实无向树来做更保险，应用性更广。看成有向树，对于本题树根就是1， scanf("%d%d",&a,&b);//为了保险，还是要判断。 G[a].push_back(b); in[b]++; } for(i=1;i<=N;i++) if(!in[i]){ root=i; break; } DP(root,0); if(f[N-P]<ans) ans=f[N-P]; printf("%d\n",ans); } return0;}/*1271111121223244548565789810这组数据输出为1*/树的中心(ural_1056Computernet)什么树的中心？树：无根树某个节点的P值：到所有节点的距离的最大值中心：P值最小的那个1.一棵树，或者有一个中心，或者有两个，但至少有一个我的做法用了下面结论：结论一：中心一定在任意一个深度最大的节点到根节点的路径上（如果有多个深度最大的点就在路径的交集上）结论二：中心在树上的最长的路径上（有多条就在交集上）所以只要任意找出一个深度最大的点，求出其它点到它的距离的最大值，顺着到根的路径就能把中心找出来了，如果最大值是奇数就有两个中心，偶数就有一个中心以下这两种解法没经过证明：1.不断的剥掉叶子，用个数组记录叶子，剥掉叶子后立即检查这个叶子的父亲，如果他父亲的度是1，则把他放到数组里，要小心只剩下2个点的时候，那时2个点就是中心了2.由于是树结构，所以可以把一棵树看成这样：(t1)(t2)一条边ei(u,v)把一棵树分成2部分，如果t1的深度>t2的，则中心在t1,若小于就在t2,如果相等就是u,v2点.这样只需要O(E),不过写的时候注意一点才行读入的时候用个par[i]记录i的父亲是谁,顺便连度数也记录了读完后,第一次把叶子找出来,这样delete那些叶子，检查他们的父亲，新的叶子一定在他们的父亲中产生，这样继续delete以下代码是根据结论来做，还有一个是用树状DP.#include<iostream>#include<vector>usingnamespacestd;#defineMN10010vector<int>G[MN];intN,par[MN];booltag[MN],visit[MN],two,finish;intd[MN],depmax,vmax,lans[2],tn;voidmy_clear(){ inti; for(i=0;i<=N;i++) { G[i].clear(); }}voidbuild(){ scanf("%d",&N); inti,b; my_clear(); for(i=1;i<N;i++) { scanf("%d",&b); G[b].push_back(i+1); G[i+1].push_back(b); }}voiddfs(intv,intfather,intdep){ inti,s,w; par[v]=father; d[v]=dep; visit[v]=true; if(dep>depmax) { depmax=dep; vmax=v; } s=G[v].size(); for(i=0;i<s;i++) { w=G[v][i]; if(!visit[w]) { dfs(w,v,dep+1); } }}voidswap(int*ans){ intt=ans[0]; ans[0]=ans[1]; ans[1]=t;}voidsolve(){ intv,i; memset(visit,false,sizeof(visit)); depmax=-1; dfs(1,-1,0); memset(visit,false,sizeof(visit)); depmax=-1;//depmax要重新清0，这点不要漏 dfs(vmax,-1,0); intk=depmax/2; intans[2]={-1,-1}; v=vmax; for(i=1;i<=k;i++) { v=par[v]; } ans[0]=v; if(N!=1&&depmax%2==1) { ans[1]=par[v]; } printf("%d",ans[0]); if(ans[1]!=-1) printf("%d",ans[1]); printf("\n");}intmain(){ build(); solve(); return0;}以下是用树状DP来做.枚举每个点，然后DFS复杂度O(N2)，超时是显然的事情。可以发现其实有很多DFS都重复做了同样的工作，产生了浪费，所以应该选择动态规划解决这个问题。树上的动规，是否直接可以写出下面的状态转移方城呢？f[i]:=max(f[son],f[father])+1废话，显然是不行的，son和father的值不可能同时得到。但是不要放弃，解决这个冲突的方法，就是采用二次动规。第一次动规做f[i]:=max(f[son])+1，第二次动规做f[i]:=max(f[i],f[father]+1)。但是存在一个问题就是如果f[father]的值是从i那里得到的，这样计算显然就错了。不要放弃，在实际操作过程中，f需要记下两个值，一个是最优值，一个是次优值，这两个值必须由不用的子结点得到。这样当最优值发生矛盾的时候，次优值一定不会矛盾。问题就解决了。复杂度O(N)十分的理想。刚开始看到这个解题报告不知道什么时候矛盾，其实这边说的不是很明白。1.做一次dfs,第一次算出每一个节点的第一大和二大的深度d[i][0],d[i][1]，并记录两个深度的值是从哪个子节点得来的f1[],f2[]，在算的过程并记录每一个节点的父亲节点p[w]。2.第二次dfs,在第一次dfs的基础上，算出每个节点v到从父亲节点走所有节点（不包括v的子节点）的最大距离存于maxd[w]中，maxd[w]={maxd[p[w]]+1,或d[p[w]][0或1]+1}。3.最后maxd[i]=max(maxd[i],d[i][0]);就是节点i到所有节点的最大距离。但是对于本题，其实可以不用做dfs，因为这个树的很特别，节点的连接是按顺序，所以可以不用dfs，直接用迭代就可以解决了。（见后面的pascal程序）其实上面的第二次dfs也可以不用，在第一次dfs的时候，记录节点dfs的编号，然后就可以用迭代了。本题也可以出个变形的题目，求出每一个节点的到所有节点的最大距离，时间复杂度O(n);其实本题就是求树的中心。程序调了很久，开始的时候出现很多错误。#include<iostream>#include<vector>usingnamespacestd;#defineMN10010intd[MN][2],N,up[MN],p[MN],f1[MN],f2[MN],maxd[MN];boolvisit[MN];vector<int>G[MN];intdfs(intv){ inti,s,t,w; visit[v]=true; s=G[v].size();/* if(s==1)//这边错了，根节点也可能s==1，不一定就是叶子节点 { d[v][0]=0; return0; }*/ d[v][0]=d[v][1]=0;//多这一个 for(i=0;i<s;i++) { w=G[v][i]; if(!visit[w]) { p[w]=v; t=dfs(w)+1; if(t>d[v][0]) { d[v][1]=d[v][0];//开始时少了这一个句,开始的时候后这一句放在下面一句的下面，错了 d[v][0]=t; f1[v]=w; } elseif(t>d[v][1]) { d[v][1]=t; f2[v]=w; } } } returnd[v][0];}voidDP(intv){ inti,s,w; visit[v]=true; s=G[v].size();/* if(f1[p[v]]==v) { maxd[v]=d[v][1]; } else { maxd[v]=d[v][0]; } if(maxd[p[v]]+1>maxd[v]) { maxd[v]=maxd[p[v]]+1; }*/ for(i=0;i<s;i++) { w=G[v][i]; if(!visit[w]) { maxd[w]=0; if(f1[p[w]]==w) { maxd[w]=d[p[w]][1]+1; } else maxd[w]=d[p[w]][0]+1;/* if(maxd[w]<d[w][0])//这个if不能放在这边算，否则会破化maxd的值，DP时就错了，如4123时就错了算出，maxd[3]=3。 maxd[w]=d[w][0];*///要确保maxd[v]不是从路径v--w这边获得的 if(maxd[p[w]]+1>maxd[w])//开始的时候这个if没有就错 { maxd[w]=maxd[p[w]]+1; } DP(w); } }}voidsolve(){ dfs(1); inti; for(i=0;i<=N;i++) { visit[i]=false; } maxd[1]=0;//DP(1)前的maxd[1]的值(即根节点的maxd值)要注意一下 DP(1); intmm=INT_MAX;//DP(1)后maxd[i]的值，并不是最终节点i到所有节点的最大距离 intans[2]={-1,-1},num=0;//而是从i出发往父亲节点走向所有节点的最大距离，不包括往i节点往下走的节点的距离 for(i=1;i<=N;i++) { maxd[i]=max(maxd[i],d[i][0]);//这边算出的才是最终的的值 if(mm>maxd[i]) { mm=maxd[i]; ans[0]=i; num=0; } elseif(mm==maxd[i]) { ans[++num]=i; } } printf("%d",ans[0]); if(num==1) { printf("%d",ans[1]); } printf("\n");}intmain(){ build(); solve(); return0;}树的最小覆盖(pku1848最少的点通过边覆盖其它所有的点)解题报告：输入有Ｎ个顶点和N-1条边的树。要你求最少的顶点集，使得这些顶点覆盖所有的其他的顶点。开始的时候以为这题更那个Strategicgame是一样题目，其实不是这样的，那题一个顶点控制的是与顶点相邻的边，问你控制所有的边最少需要几个顶点，这题是顶点覆盖相邻的顶点。这个导致如果用树状DP的话，状态和状态转移方程不同。但是这两题都可以用贪心来做。//f[i][0]表示以i为根的子树，根不取，所有点都满足条件的最优值//f[i][1]表示以i为根的子树，根取，所有点都满足条件的最优值//f[i][2]表示以i为根的子树，根不取，除了根之外其他点都满足条件的最优值(根满足也行不满足也行)这样设状态可以过，也有其他几种不同的表示方法吧。不过好像最少都要三个状态的对上面的三个状态重新定义：f[i][0]表是根不取，但是根被子节点控制的最优值f[i][1]根取的时候的最优值f[i][2]根不取，根节点被子节点控制和或不被子节点控制状态转移的方程：f[i][1]=1+min{f[k][v]}k=0,1,2顶点为v为顶点i的儿子。f[i][2]=min{f[0][v],f[1][v]};表示i节点不取，但是子节点都必须满足条件，f[i][0]=如果f[i][2]的最有值中的子节点有一个放了，那么f[i][0]=f[i][2],否则选择一个子节点放的，其他还是取最小值（不放）最优值#include<iostream>usingnamespacestd;constintmaxn=10000;typedefstruct{ intv; intnext;}EDGE;EDGEe[2*maxn];inth[maxn];intf[3][maxn];inten,N;boolinput(){ if(scanf("%d",&N)==EOF) { returnfalse; } inti,a,b; memset(h,-1,N*sizeof(int)); en=0; for(i=1;i<N;i++) { scanf("%d%d",&a,&b); --a; --b; e[en].v=a; e[en].next=h[b]; h[b]=en; ++en; e[en].v=b; e[en].next=h[a]; h[a]=en; ++en; } returntrue;}inlineintmin2(inta,intb){ returna<b?a:b;}inlineintmin3(inta,intb,intc){ if(a>b) a=b; if(a>c) a=c; returna;}voiddfs(intv,intp){ boolplate=false; boolleaf=true; f[0][v]=f[2][v]=0; f[1][v]=1; inti,dif=INT_MAX; for(i=h[v];i!=-1;i=e[i].next) { if(e[i].v!=p) { leaf=false; dfs(e[i].v,v); f[1][v]+=min3(f[0][e[i].v],f[1][e[i].v],f[2][e[i].v]); if(f[1][e[i].v]<=f[0][e[i].v]) { f[2][v]+=f[1][e[i].v]; plate=true; } else { f[2][v]+=f[0][e[i].v]; if(f[1][e[i].v]-f[0][e[i].v]<dif) { dif=f[1][e[i].v]-f[0][e[i].v]; } } } } if(leaf) { f[0][v]=1; f[1][v]=1; f[2][v]=0; return; } f[0][v]=f[2][v]; if(!plate) { f[0][v]+=dif; }// printf("%d%d%d%d\n",v,f[0][v],f[1][v],f[2][v]);}voidsolve(){ f[0][0]=f[1][0]=0; dfs(0,-1); intans=min2(f[0][0],f[1][0]); printf("%d\n",ans);}intmain(){ while(input()) { solve(); } return0;}蜗牛找房子（pkuTheLostHouse）题目大意：蜗牛的房子遗失在了一棵树的某个叶子结点上，它要从根结点出发开始寻找它的房子。有一些中间结点可能会住着一些虫子，这些虫子会告诉蜗牛它的房子是否在以这个中间结点为根的子树上，这样蜗牛就不用白跑路了。当然，如果有些结点没有住着虫子的话，那么可怜的蜗牛只有靠自己决定访问顺序来探索了。假设蜗牛走过一条边的耗费都是1，且房子遗失在每个叶子结点的概率都是相等的，那么请问蜗牛找到他的房子的最小数学期望值？SampleInput5-1N1N1Y3N3N10-1N1Y1N2N2N2N3N3Y8N8N6-1N1N1Y1N3N3N0SampleOutput3.00005.00003.5000我们约定，树上的结点数n最多为1000，每个结点的分叉数k最多为8。例如在下面的这棵树当中：蜗牛从根结点1出发开始寻找它的房子，它的房子可能遗失在2、4、5。在结点3上住着一只虫子，它会告诉蜗牛，以3为根的子树上是否有蜗牛的房子。蜗牛有两种走法。蜗牛可以先访问2，如果它在那儿不能找到房子，那么它要回到根结点1，再通过3来访问结点4（或5），如果还是不能找到它的房子，那么它又要回到结点3，再去访问结点5（或4）。在这种走法中，当房子分别位于2、4、5的时候，蜗牛需要走的步数分别是1、4、6，期望值是(1+4+6)/3=11/3。显然，这种走法没有充分发挥虫子在这里起到的作用。在另一种走法中，蜗牛先访问结点3，它可以从住在3上的虫子那里得知它的房子是否存在于4或5的信息。在这种走法中，当房子分别位于2、4、5的时候，蜗牛需要走的步数分别是3、2、4，期望值是(3+2+4)/3=3。这种走法合理的利用了虫子提供的信息，得到了更优的数学期望值。算法分析：不难分析出本题的大体模型是用树的动态规划来求解。用Fa[i]表示蜗牛的House在i为根的子树上的期望和，用Fb[i]表示蜗牛的House不在i为根的子树上的时候遍历该子树需要的时间，用Leaves[i]表示i为根的子树上叶子节点的数目。问题的解答就是Fa[根结点]/Leaves[根结点]。如果结点u有k个儿子,我们按照S[1]..S[k]进行访问，Fa[u]的计算方式是：Fa[u]=0;Fb[u]=0;fori=1tokdobeginFa[u]=Fa[u]+(Fb[u]+1)×Leaves[S[i]]+Fa[S[i]];Fb[u]=Fb[u]+Fb[S[i]]+2;end;用公式的形式可以表示为：①现在的问题就是如何决定访问儿子的顺序，不同的访问顺序会产生不同的Fa[u]。我们要使得Fa[u]尽量的小。一种直观的方法是k！枚举访问顺序，总体复杂度是O(nk!)，实在是很低效。用状态压缩的动态规划进行二次动规的话，可以将复杂度降为O(n2kk)，勉强可以接受了。（注：由于状态压缩的动态规划不是本文的重点，故这里不做展开）但是我们的研究并没有因此停止!我们尝试用贪心的思想来分析问题：考虑一种访问顺序中的两个相邻元素v和v+1，如果交换v和v+1之后得到的值不如交换前的值，那么v一定在v+1的前面了。具体证明如下：我们对公式①来进行一些处理。可以看出，交换v和v+1之后，对和是不会产生任何影响的，关键是看是增大了还是减小了。把交换前和交换后的值做差：最后得到的则只跟元素v和v+1的信息有关，于别的元素的排列情况无关，所以元素v和v+1是可比的。证毕。另外，根据这个结果，可以得出另一个结论：如果A一定放在B前，B一定放在C前，可以推导出A一定放在C前。证明：两式相乘得到：证毕。上面这个结论说明，本题中的“可比性”是可以传递的，因此可以根据这个性质确定出一个全序关系，因而省去了枚举排列的部分，只需要对所有元素进行一次排序即可。时间复杂度为O(nklog2k)，非常优秀。自己的解题报告：本题就是按照论文里的方法写的，不过对于比较函数，开始时候按照里面的来写错了很错次，试了很多比较函数都是错的。一下这两种比较函数都是错的。boolcmp1(inta,intb){ return(fb[a]*1.0/leaves[a])<(fb[b]*1.0/leaves[b]);}boolcmp2(inta,intb){ return(fa[a]*1.0/leaves[a])>(fa[b]*1.0/leaves[b]);}还写了一种比较函数在cmp1相等的情况下，在比较cmp2,也是错的。就是看了讨论里的说法：访问每一棵子树失败的代价设为wi,相应子树的叶子数目设为li对wi/li排序之后的顺序就是子树的访问顺序在注意一下递推式子里面的数，其实很容易想到比较函数：其实上面乘的我们也可以写成除的，可以写成相应的乘的这样保证不会有精度问题。boolcmp(inta,intb)//这个比较函数注意，开始的时候写很多个{ return(fb[a]+2)*leaves[b]<(fb[b]+2)*leaves[a];}#include<iostream>#include<algorithm>usingnamespacestd;constintmaxn=1010;intfa[maxn],fb[maxn],leaves[maxn];boolw[maxn];typedefstruct{ intv; intnext;}Edge;Edgee[maxn];inth[maxn];intn,en;boolinput(){ scanf("%d",&n); if(n==0) returnfalse; chartmp[2]; intv; en=0; memset(h,-1,sizeof(h)); scanf("%d%s",&v,tmp); if(tmp[0]=='Y') { w[1]=true; } inti; for(i=2;i<=n;++i) { scanf("%d%s",&v,tmp); e[en].v=i; e[en].next=h[v]; h[v]=en; en++; if(tmp[0]=='Y') { w[i]=true; } else { w[i]=false; } } returntrue;}boolcmp(inta,intb)//这个比较函数注意，开始的时候写很多个{ return(fb[a]+2)*leaves[b]<(fb[b]+2)*leaves[a];}voiddfs(intv){ fa[v]=fb[v]=0; inti; leaves[v]=0; if(h[v]==-1) { leaves[v]=1; return; } intseq[8],top=0;//这边的seq必须是局部变量，因为有递归下去，全局的话，值会变 for(i=h[v];i!=-1;i=e[i].next) { dfs(e[i].v); seq[top++]=e[i].v; leaves[v]+=leaves[e[i].v]; } sort(seq,seq+top,cmp); for(i=0;i<top;++i) { fa[v]=fa[v]+(fb[v]+1)*leaves[seq[i]]+fa[seq[i]];//开始的时候这边不理解，看看样例就知道了 fb[v]=fb[v]+fb[seq[i]]+2; } if(w[v]) { fb[v]=0; }}voidsolve(){ dfs(1); printf("%.4lf\n",1.0*fa[1]/leaves[1]);}intmain(){ while(input()) { solve(); } return0;}选课(vijos1180)描述Description 学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。例如:表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都一定已被选修过。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。 输入格式InputFormat 输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。 输出格式OutputFormat 输出文件只有一个数,实际所选课程的学分总数本题是树形DP，有一点要注意，就是本体不一定就是一个树，可能是森林，多一个零节点，建成一课树。开始的时候一直不知道怎么从叶子往根DP，还是从根到叶子DP，因为认为对于内部节点，如果其深度为h,那么它只有f[v][k](k>=h)才有状态，才有值，所以开始的时候认为应该从根到叶子DP,而且还要多几个参数，比如节点深度,子树节点的个数等等。后来想通了，可以从叶子往根DP，也不用深度这个参数。对于每个节点，其值f[v][1~~K]（k为子树的节点的个数）有状态，f[1]=cost[v]其儿子只对v节点的f[v][2]才有影响，而对于v的父亲节点，v只对f[w][2]有影响，而v的儿子f[v][2]的值只对f[w][3]才有影响，只样一直传递上去，最后就是答案了，对于每一个节点，没有f[v][0]这个状态，DP的时候不用考虑0的情况。#include<iostream>#include<vector>usingnamespacestd;vector<int>G[301];intf[301][301]={0},c[301],N,M,in[301]={0};inlineintmymax(inta,intb){ returna>b?a:b;}intDP(intv){ intt,w,now,i,j,k; t=1; f[v][1]=c[v]; for(i=0;i<G[v].size();i++) { w=G[v][i]; now=DP(w); for(j=t;j>=1;j--) { for(k=1;k<=now;k++) { f[v][j+k]=mymax(f[v][j+k],f[v][j]+f[w][k]); } } t+=now; } returnt;}intmain(){ inti,j,b; scanf("%d%d",&N,&M); for(i=1;i<=N;i++) { scanf("%d%d",&b,&c[i]); if(b!=0){ G[b].push_back(i); in[i]++; } } for(j=1;j<=N;j++) if(in[j]==0) G[0].push_back(j); c[0]=0; DP(0); printf("%d\n",f[0][M+1]);//之所以要M+1是因为多了0，这个课程 return0;}树上多少对节点距离少于给定值(pku1741)题目意思：给你一个含有N个节点的树，问你树中有多少个节点对其距离小于K。SampleInput5412313114235100SampleOutput8算法分析：本题是DFS+归并排序。归并排序真得需要好好理解一下，很多场合都用的上。归并排序还可以用来求逆序数。对于本题：先DFS算出根结点的当前子节点为根的子树中所有节点在根节点的距离存于dist[to+1~st]中，然后再算当前子节点为根的子树中所有节点到已经遍历过的节点的距离小于K的对数.（算的时候要利用排好序的作用），然后然归并排序把to+1~st归并到已经遍历的节点当中。本程序很简单，但是如果你不会，写程序就很困难，本程序很有技巧性，如cnt的功能，如何判断当前子树处理到了那个节点，返回值的设置等！#include<stdio.h>#include<string.h>#defineMN10032structEdge{ intver,next,wt;}E[MN*2];inth[MN];intdist[MN],t[MN],N,K,cnt,ans;intDFS(intv,intp){ intfrom,to,st,i,j,r,idx,w; from=to=cnt++; dist[to]=0;//初始距离为0 for(idx=h[v];idx!=-1;idx=E[idx].next) { w=E[idx].ver; if(w!=p) { st=DFS(w,v); for(i=to+1;i<=st;i++)//这个别忘，加上后才是到根节点的距离 { dist[i]+=E[idx].wt; } for(i=from,j=st;j>to;j--)//利用排序的作用 { while(i<=to&&dist[j]+dist[i]<=K) i++; ans+=i-from; } for(r=from,i=from,j=to+1;i<=to&&j<=st;) { if(dist[i]<dist[j]) t[r++]=dist[i++]; else t[r++]=dist[j++]; } while(i<=to){ t[r++]=dist[i++]; } while(j<=st) { t[r++]=dist[j++]; } for(i=from;i<=st;i++) { dist[i]=t[i]; } to=st; } } returnto;}intmain(){ inti,a,b,c,now; while(scanf("%d%d",&N,&K)!=EOF) { if(!N&&!K) break; now=1; memset(h,-1,sizeof(h)); for(i=1;i<N;i++) { scanf("%d%d%d",&a,&b,&c); E[now].wt=c; E[now].ver=a; E[now].next=h[b]; h[b]=now; now++; E[now].wt=c; E[now].ver=b; E[now].next=h[a]; h[a]=now; now++; } cnt=1; ans=0; DFS(1,-1); printf("%d\n",ans); } return0;}给树加最少边，使每边都只属于一个环(Pku1848Tree)SampleInput7121335345657SampleOutput2[动态规划]pku18