| ||||||||||
| 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,所以用贪心,一开始没标记叶子节点,从后往前贪,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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator