【题意】

给定长方形的两条边h和w,你可以从给出的n个数字中随意选出一个x,把h或者w乘上x（每个x最多用一次），直到能够把一个长为a宽为b的长方形装下为止。问最小的x选择次数。

首先，同样选一个数字，数字大的肯定较优，因此先给x从大到小排序；

现在的问题是同一个x，要给h乘还是w乘。

首先，题目的数据范围是100 000,所以最多只需要34个x(log100 000=17),但是如果这样暴搜的话时间复杂度是2^34,会超时。

但是，我们注意到，从某一位开始，后面都是2的话，就不需要再搜索了，因为2分配给谁都一样，只需要有一个while循环跑一下就可以了，这个剪枝可以把2^34减到2^22(log3(100 000)=11)，这样就完美解决了这道题。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 9 using namespace std;10 const int maxn=1e5+5;11 int a,b,h,w,n;12 int c[maxn];13 int flag;14 int ans;15 bool cmp(int a,int b)16 {17 return a>b;18 }19 void dfs(int aa,int bb,int num)20 {21 if(!aa&&!bb)22 {23 ans=min(ans,num);24 return;25 }26 if(num>=n)27 {28 return;29 }30 if(c[num]!=2)31 {32 if(aa) dfs(aa/c[num],bb,num+1);33 if(bb) dfs(aa,bb/c[num],num+1);34 }35 else36 {37 while(aa)38 {39 num++;40 aa/=2;41 }42 while(bb)43 {44 num++;45 bb/=2;46 }47 ans=min(ans,num);48 return;49 }50 }51 int main()52 {53 while(~scanf("%d%d%d%d%d",&a,&b,&h,&w,&n))54 {55 for(int i=0;i
             
              =a&&w>=b||h>=b&&w>=a)61 {62 printf("0\n");63 continue;64 }65 ans=n+1;66 dfs((a-1)/h,(b-1)/w,0);67 dfs((a-1)/w,(b-1)/h,0); 68 if(ans<=n)69 {70 printf("%d\n",ans);71 }72 else73 {74 printf("-1\n");75 }76 }77 return 0;78 }
             
            
           
          
         
        
       
      

注意：

1. dfs不能得到一个值就认为是最优解.......

2. 

1 if(c[num]!=2)2     {3         if(aa) dfs(aa/c[num],bb,num+1);4         if(bb) dfs(aa,bb/c[num],num+1);5     }

没有if判断会超时