[413D][搜索]D

http://codeforces.com/contest/799/problem/D

解题关键：因为3^11>100000，所以若只把2单独拿出，最多只需要暴力2^11次，故只需要dfs一下即可。

 1 #include<bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 typedef long long ll;
 5 ll a,b,h,w,n,d[100002],ans;
 6 void dfs(ll aa,ll bb,ll x){
 7     if(aa>=a&&bb>=b){ ans=min(ans,x);return;}
 8     if(x==n+1) return;
 9     if(d[x]==2){
10         while(aa<a){aa<<=1,x++;}
11         while(bb<b){bb<<=1,x++;}
12         ans=min(x,ans);
13         return;
14     }
15     
16     if(aa<a) dfs(aa*d[x],bb,x+1);
17     if(bb<b) dfs(aa,bb*d[x],x+1);
18 } 
19 int main(){
20     cin>>a>>b>>h>>w>>n;
21     for(ll i=0;i<n;i++) cin>>d[i];
22     sort(d,d+n,greater<ll>());
23     ans=n+1;
24     dfs(h,w,0);
25     dfs(w,h,0);
26     ans=(ans==n+1?-1:ans);
27     cout<<ans<<endl;
28     return 0;
29 }