【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;
}

4 thoughts to “【Codeforces 799D】Field expansion”

  1. Does your site have a contact page? I’m having problems locating it but,
    I’d like to send you an email. I’ve got some suggestions for your blog
    you might be interested in hearing. Either way,
    great blog and I look forward to seeing it grow over time.

发表评论

电子邮件地址不会被公开。 必填项已用*标注