Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
题解树形DP PS(一个圈至少有3个点!!!) DP[I][0] 表示以i点为根树,全部点添加成圈,需要添加边数 DP[I][1] 表示以i为根树,全部点添加成圈,但是i不属于任何圈,需要添加边数 DP[I][2] 表示以i为根树,全部点添加成圈,但是从i点出发存在一条长度至少为2的路 径不属于任何圈,需要添加边数 具体做法,求出某个点所有儿子的dp[i] ,然后暴力状态转移,得出该点DP[I] ( n^3) 优化:从一个点的儿子的DP,求出该点DP,可以内嵌一个动态规划,时间复杂度降到n^2 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator