【Codeforces 799D】Field expansion

相关链接

题目传送门：http://codeforces.com/contest/799/problem/D

解题报告

不难发现，至多只会使用$O(2 \log 10^5)$个物品
于是定义$f_i$表示长为$i$时，宽最多为多少
暴力转移即可，时间复杂度：$O(10^5 \log 10^5)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int INF = 1e9;

int n,v[N],f[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline bool cmp(int a, int b) {
	return a > b;
}

inline int solve(int a, int b, int h, int w) {
	memset(f, 0, sizeof(f));
	f[min(h, a)] = min(b, w);
	int ans = 1;
	for (int j=1;j<=n;j++,ans++) {
		for (int i=a;i;i--) {
			if (f[i]) {
				int tt = min((LL)a, (LL)i * v[j]);
				f[tt] = max(f[tt], f[i]);
				if (tt == a && f[i] == b) {
					return ans;
				}
				tt = min((LL)b, (LL)f[i] * v[j]);
				f[i] = tt;
				if (i == a && tt == b) {
					return ans;
				}
			}
		}
	}
	return INF;
}

int main() {
	int a = read(), b = read();
	int h = read(), w = read();
	n = read();
	for (int i=1;i<=n;i++) {
		v[i] = read();
	}
	sort(v+1, v+1+n, cmp);
	n = min(n, 34);
	if ((h >= a && w >= b) || (h >= b && w >= a)) {
		puts("0");
		exit(0);
	}
	int ans1 = solve(a, b, h, w);
	int ans2 = solve(a, b, w, h);
	if (ans1 >= INF && ans2 >= INF) {
		puts("-1");
	} else {
		printf("%d\n",min(ans1, ans2));
	}
	return 0;
}