题意：原本有矩形 a*b，给出一个矩形 h*w，和一个序列 a[]，可以把 h 或 w 扩大 a[i] 倍，每个 a[i] 只能用一次。 问最少要用到 a[] 里多少个数，使得扩大后的矩形 h*w 可以将矩形 a*b 放入。
tags： 根据题目情况来暴搜，，，骚的一匹。。
1】先考虑最坏的情况，即 a*b 都是 1e5， h*w 都是 1，而所有a[] 都是 2，因为 (2^17) > 1e5，那我们至少要用到 34 个 2 。如果直接暴搜，每个数要枚举分配给 h, w 两个数，就是 O(2^34) 的时间，显然超时。
2】而如果有数是大于 2 的，以 3 为例，因为 (3^11) > 1e5，所以大于 2 的数最多用到 22 个。 O(2^22) 的时间，这可以接受。
所以对大于 2 的数直接暴搜，然后对剩下的 2，就不需要暴搜了，因为 2 分配给出谁都是一样的。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 200005; bool cmp(int a, int b) { return a>b; } int n; ll h1, w1, h2, w2, a[N]; bool check(int cnt, ll h, ll w) { while(w<w1 && cnt) w*=2, --cnt; while(h<h1 && cnt) h*=2, --cnt; if(h>=h1 && w>=w1) return true; return false; } bool dfs(int x, ll hh, ll ww, int now) { if(now-1==x) { if(hh>ww) swap(hh, ww); if(hh>=h1 && ww>=w1) return true; return false; } if(a[now]==2) { int cnt = x-now+1; if(check(cnt, hh, ww) || check(cnt, ww, hh)) return true; return false; } if(dfs(x, hh*a[now], ww, now+1)) return true; if(dfs(x, hh, ww*a[now], now+1)) return true; return false; } int main() { scanf("%lld%lld%lld%lld%d", &h1, &w1, &h2, &w2, &n); rep(i,1,n) scanf("%lld", &a[i]); if(h1>w1) swap(h1, w1); if(h2>w2) swap(h2, w2); if(h2>=h1 && w2>=w1) return 0*printf("0 "); sort(a+1, a+1+n, cmp); rep(i,1, min(n, 34)) if(dfs(i, h2, w2, 1)) return 0*printf("%d ", i); printf("-1 "); return 0; }