标签-树形dp

庆祝第100篇文章完成!题意一棵有边权的树,有的节点是转播站,有的节点是用户节点。要让用户看到电视,代价为根节点到当前用户节点的路径和,重复的路径不重新计算。每个用户可以支付一定的钱。求在不亏本的情况下,最多可以让多少个用户看到电视。其中点数 $N\le 3000$ 。题解树上背包的裸题。用 $f[x][i]$ 表示在以 $x$ 节点为根的子树中选 $i$ 个用户的最大收益。转移方程式为:$...
   题解    0 条评论
提高+/省选-
题意在树上放一些山贼集团的分部,每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点,如果它被多个分部收保护费,就可能产生收益或损失。求最优的放置方法,可以得到最大利润。其中点数 $N\le 100$ ,分部个数 $P\le 12$ 。题解看到 $P$ 的范围,显然可以对节点上放置分部的状态进行状压。因为每个分部收取的...
   题解    0 条评论
省选/NOI-
题意求所有在树上直径的节点。点数 $N\le 200000$ 。题解我百度谷歌搜了一圈硬是没看到一个像样的题解,去提交记录里面看代码读懂的方法。先跑第一遍 $dfs$ ,记录以 $x$ 为根的子树中深度的最大值 $mx[x]$ 和次大值 $mx2[x]$ ,两者相加再 $+1$ 即为这个子树的直径。然后再跑一遍,对于每个节点 $x$ ,遍历所有子节点 $y$ ,并对子节点向上最大深度 $up...
   题解    0 条评论
题意一棵无根树,要求根节点到每个叶子的路径上都至少有一个有色节点。给出根节点到每个叶子节点路径上最后一个有色节点的颜色,求有色节点个数最小值。其中点数 $N\le 1000$ ,叶子节点个数 $M\le 5021$ 。(我按个人习惯反过来了)题解树形dp,用 $f[x][0/1]$ 表示以 $x$ 为根的子树,最后一个有色节点颜色为黑/白的最优情况。考虑状态转移,如果子节点和自己要求一样,则...
   题解    0 条评论
提高+/省选-
时隔半年再来做发现还是不会,于是乎还是写个总结吧。题意一棵二叉树,只能保留 $Q$ 条边,求剩下的边最大边权和。其中点数 $N\le 100$ ,$Q\le 100$ 。题解用 $f[x][j]$ 表示在以 $x$ 为根的子树上保留 $j$ 条边的最优情况。搜索时枚举 $x$ 的子节点 $y$ ,然后类比背包枚举以 $y$ 为根的子树保留的边数 $k$ ,得到状态转移如下:$f[x][j]=...
   题解    0 条评论
提高+/省选-
又是一道我看了题解才知道怎么做的题,我还是太弱了。题意每个骑士都有一个自己痛恨的骑士(不会恨自己),这俩不能在一起,每个骑士有个能力值,问怎么组合使总的能力值最大。其中骑士的人数 $N\le 10^{6}$ 。题解分(看)析(题)题(解)目可以发现,如果将每个关系之间连一个双向边,每个连通块都有且仅有一个环,所以整个图就是一个基环森林,然后拆一条边分成两棵树各跑一遍树形dp即可。拆开看以后也...
   题解    0 条评论
省选/NOI-
重题,双倍经验。https://llf0703.com/p/uva-1292.html而且uva的题还有多组输出,删掉就行了。struct Edge{ int next,to; } edge[3005]; int head[1505],n,m,a,b,c,cnt,f[1505][2],out[1505]; inline void add(int u,int v) { edg...
   题解    0 条评论
提高+/省选-
跟舞会那道题差不多,如果父节点没有取那么所有子节点都必须取;如果父节点取了,子节点取或不取皆可。$$\begin{cases} f[i][1]=\sum \min(f[j][0],f[j][1]) \\ f[i][0]=\sum f[j][1] \end{cases}$$需要注意的是题目中已经把子树说明了,这就意味着只能有一个点作为根节点,所以应该连单向边,并且事先找到那个点作为根节点。st...
   题解    0 条评论
提高+/省选-
大水题,题意就跟题目名一样,决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ,显然要当前子树和要大于0我们才会取,然后dfs即可。方程式:$$f[x]+=max(f[y],0)$$struct Edge{ int next,to; } edge[32005]; int s[16005],n,m,a,b,c,cnt,head[16005],w[16005],ans; inli...
   题解    0 条评论
普及+/提高
题意要从 $N$ 门课中选出 $M$ 门,有的课有价值和先决条件,求价值总和最大值。其中 $N,M\le 300$ 。题解1.多叉转二叉我们用 $f[x][cnt]$ 表示当前x节点,在以 $x$ 为根的子树中选 $cnt$ 个节点。对于每一个节点,可以有选和不选两个选项,如果不选就把 $cnt$ 全都给兄弟节点,也就是右节点;如果要选就把 $cnt$ 分别分配给 $x$ 的兄弟和以 $x$...
   题解    0 条评论
提高+/省选-