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

第一道树DP~

Posted by cssdnx at 2011-07-25 11:17:15 on Problem 1463
dproot[k]表示在节点k处添一个士兵,以它为根的子树共需要多少个士兵,all[k]表示以它为根的子树共需要多少个士兵.

对于叶子: dproot[i]=1, all[i]=1
对于非叶子: dproot[i]=1+∑all[j](j是i的儿子), 
             all[i]=min(dproot[i],∑dproot[j](j是i的儿子) );

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