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

Re:给个简单证明吧

Posted by Mandolin23 at 2011-04-14 05:44:01 on Problem 1065
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:
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