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:虽然AC了,不过还是有点质疑

Posted by zjd1333 at 2008-12-22 13:10:16 on Problem 1011
In Reply To:虽然AC了,不过还是有点质疑 Posted by:new_star at 2008-02-18 07:10:56
> //木棍长度已按升序排序,已经完成k根,第k+1根已完成长度ll,应该用t以后的木棍填充
> bool search( int k, int ll, int t )
> {	int p;
> 	if ( k == num ) return true;
> 	for ( int i = t; i <= sticksNum; i++ ) {
> 		if ( ! used[i] ) {
> 			if ( (p = ll+stick[i]) < goalLen ) {
> 				used[i] = true;
> 				if ( search( k, p, i+1 ) ) return  true;
> 				used[i] = false;
> 			}
> 			else if( p == goalLen ) {
> 				used[i] = true;
> 				if( search( k+1, 0, 1 ) ) return true;
> 				used[i] = 0;
> 				break;//开始没有这条语句,结果TLE
> 			}
> 			if ( ll == 0 ) break;
> 		}
> 	}
> 	return false;
> }
> 疑问:如果存在某个长度正好填满一根原始木棍,就真的不该考虑其他长度的木棍了么?
>       刘泸佳的书上是认可的,如果能用更长的原始木棍,长度将会超过t,显然不行;
>       如果使用更短的,即使存在某个也能填满木棍的方法,该方法也一定不会比用大木头更有希望获得可行解。
>       这样,一旦发现某木棍能填满该原始木棍,就没有必要考虑其他木棍了,
>       时间效率大大提高,数据不到0.01秒解出。
>       正准备证明这个结论,大家一起讨论下

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