 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
用局部调整的思想In Reply To:W3=2,W2=2 Posted by:ZaakDov at 2009-10-08 21:43:24 假设交换相邻的两颗子树的选择顺序，设P1,P2为选他们的概率，A1,A2为房子确实在上面所需的步数，B1,B2为实际上不在上面所需的步数，则 调整后:Delta=P1*A1+P2*(B1+A2)-P2*A2-P1*(B2+A1)=P2*B1-P1*B2 于是Delta<0 <=> B1/P1<B2/P2 而P=L(这颗子树所包含的叶子树)/总得叶子树 故P1/P2=L1/L2 即Delta<0 <=> B1/L1<B2/L2 而题设情况即为Delta<0 于是应按照B/L排序 即遍历此子树所需步数/其所含叶子树 Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
