cboy__

分类

题解(3)

/ 注册

全部文章（共3篇）

Cell Phone Network——（最小点覆盖-树形DP）

题意 • 给你一棵无向树，问你最少用多少个点可以覆盖掉所有其他的点。• （一个点被盖，它自己和与它相邻的点都算被覆盖）思路最小的点覆盖确定三种状态注意边界情况，设立哨兵 or 特判 0：覆盖u， 1：被son覆盖（有点复杂：至少被一个v覆盖）根据贡献来，来，差值从小到大排序排序后，...

2020-08-17

1 1090

没有上司的舞会——树形DP

题意最大点权独立集思路树形dp维护每个点取or 不取的状态 WA的点转移方程错误： u不取，子结点可以取或者不取，导致wa了2发。题目链接 //#pragma GCC optimize(2) //#pragma GCC target ("sse4") #include<bits...

2020-08-13

0 602

二叉苹果树——树形DP-n^3枚举

题意以1为根节点，保留q个边与1连通。最大的边权和。思路 ,暴力？ or or 每个结点取子树条边，暴力n^2枚举，表示以为根的子树保留条边的最大权值和。dp转移方程前提条件：题目链接 //#pragma GCC optimize(2) //#pragma GCC targ...

2020-08-13

0 680