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 |
Re:给个简单证明吧In Reply To:给个简单证明吧 Posted by:Snow_storm at 2011-03-16 02:56:48 把stick看成一个点,对于点i,j: 如果满足 s[i].l<=s[i].l && s[i].w<=s[i].w 说明有一条有向边(i, j); 构完图后,题目转化为求图的最小覆盖问题! 而根据贪心算法,排序后,所有的有向边都是排在前面的点指向后面的点。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator