http://codeforces.com/contest/799/problem/D
【题意】
给定长方形的两条边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)，这样就完美解决了这道题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm> using namespace std;
const int maxn=1e5+;
int a,b,h,w,n;
int c[maxn];
int flag;
int ans;
bool cmp(int a,int b)
{
return a>b;
}
void dfs(int aa,int bb,int num)
{
if(!aa&&!bb)
{
ans=min(ans,num);
return;
}
if(num>=n)
{
return;
}
if(c[num]!=)
{
if(aa) dfs(aa/c[num],bb,num+);
if(bb) dfs(aa,bb/c[num],num+);
}
else
{
while(aa)
{
num++;
aa/=;
}
while(bb)
{
num++;
bb/=;
}
ans=min(ans,num);
return;
}
}
int main()
{
while(~scanf("%d%d%d%d%d",&a,&b,&h,&w,&n))
{
for(int i=;i<n;i++)
{
scanf("%d",&c[i]);
}
sort(c,c+n,cmp);
if(h>=a&&w>=b||h>=b&&w>=a)
{
printf("0\n");
continue;
}
ans=n+;
dfs((a-)/h,(b-)/w,);
dfs((a-)/w,(b-)/h,);
if(ans<=n)
{
printf("%d\n",ans);
}
else
{
printf("-1\n");
}
}
return ;
}
注意：
1. dfs不能得到一个值就认为是最优解.......
2.
if(c[num]!=)
{
if(aa) dfs(aa/c[num],bb,num+);
if(bb) dfs(aa,bb/c[num],num+);
}
没有if判断会超时