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:虽然AC了,不过还是有点质疑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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator