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 summerandautumn at 2008-11-19 11:14:17 on Problem 1463 and last updated at 2008-11-19 11:15:29
不会树形dp,所以用贪心,一开始没标记叶子节点,从后往前贪,AC了,后来发现这样不行,比如这组数据:
4
3:(1) 2
2:(2) 1 0
1:(0)
0:(0)
应该是输出1,放在2就行了,但我AC的程序输出2,后来改成从叶子节点开始,从前往后贪,比较函数是这样的:
bool operator < (const node &a)const 
{
   return leaf > a.leaf;//叶子节点为1,非叶子节点为0
}
但WA了,后来比较函数改成
bool operator < (const node &a)const 
{
    return leaf > a.leaf || (leaf == a.leaf && pos > a.pos);
},就AC了
这我很不解,题目没说节点的序号是从小到大排吧

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