经历了各种TLE,各种WA,还有一次RE,终于在网上找到两句至理名言,靠这两个剪枝,在北大上AC了这道错了25次的1011.
但不行的是在Hdu,依然WA中,预知后事如何,请听下回分解。
强大的剪枝!
1.搜索每根大木棍的时候,如果因为安放了第一段木棍就无法提供合理解的时,就不用去试探其他小木棍在第一段位置的情况了。所以回溯到上一个大木棍的搜索,是第一个大木棍的第一段出现问题,那么该长度肯定不符合要求。

2.每个大木棍的最后一段,如果不合要求,那么也不用去试图去安放其他的小木棍了,直接回溯到上段木棍即可。因为,换成更小的木棍,即便也可使木棍填满,小木棍也有可能在将来的时候无法安放。简单的说,如果它不行,采用别的更小的木棍也不行;如果它可以,采用别的更小的木棍也一定可以。

#include<stdio.h>
#include
<algorithm>
#include
<string.h>
using namespace std;
int a[100],n,sum, get, mark[100];
int cmp(int c, int b)
{
    
return c>b;
}
int dfs(int nowlen, int nowget, int nowi)
{
    
for(int i=nowi; i<n; i++)
        
if(mark[i]==0 && nowlen>=a[i]){
            mark[i]
=1;
            
if(nowlen>a[i]){
                
if(dfs(nowlen-a[i], nowget, i+1)==1)
                    
return 1;
                
else if(nowlen==sum/get//剪枝1
                { mark[i]=0;    return 0; }
            }
            
else if(nowlen==a[i]){
                
if(nowget+1==getreturn 1;
                
if(dfs(sum/get, nowget+10)==1)
                    
return 1;
                
else{
                    mark[i]
=0;//剪枝2
                    return 0;
                }
            }
        mark[i]
=0;
        }


    
return 0;
}
int main()
{
    
int i,j,k;
    
while(scanf("%d",&n) && n){
        sum
=0;
        memset(a, 
0sizeof(a));
        
for(i=0; i<n; i++){
            scanf(
"%d",&a[i]);
            sum
+=a[i];
        }
        sort(a, a
+n, cmp);
        
get=sum/a[0];
        
while(sum%get!=0){
            
get--;
        }
        
while(1){
            memset(mark, 
0sizeof(mark));
            
if(dfs(sum/get00)==1)
                
break;
            
else{
                
get--;
                
while(sum%get!=0){
                    
get--;
                }
            }
        }
        printf(
"%d\n",sum/get);
    }
    
return 0;
}