Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

题解

Posted by lzqxh at 2011-03-13 13:51:12 on Problem 1848
树形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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator