| ||||||||||
| 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