arrow_upward

标签-树形dp

我从树形dp的分类点进来的,然后看了下题,这tm跟树形dp有毛关系啊。又是一道我看了题解才知道怎么做的题,我还是太弱了。题意:每个骑士都有一个自己痛恨的骑士(不会恨自己),这俩不能在一起,每个骑士有个能力值,问怎么组合使总的能力值最大。分(看)析(题)题(解)目可以发现,如果将每个关系之间连一个双向边,每个连通块都有且仅有一个环,所以整个图就是一个基环森林,然后拆一条边分成两棵树各跑一遍树形...
   题解    0 条评论
省选/NOI-
重题,双倍经验。https://blog.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) { ...
   题解    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 条评论
普及+/提高
似乎有直接树形dp的做法,但我还是多叉转二叉做的。我们用 $f[x][cnt]$ 表示当前x节点,在以 $x$ 为根的子树中选 $cnt$ 个节点。对于每一个节点,可以有选和不选两个选项,如果不选就把 $cnt$ 全都给兄弟节点,也就是右节点;如果要选就把 $cnt$ 分别分配给 $x$ 的兄弟和以 $x$ 为先修的课程,也就是左节点。第二种情况需要枚举一下 $cnt$ 分配的个数。所以我们...
   题解    0 条评论
提高+/省选-