相关链接
题目传送门: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; }
Way cool, some valid points! I appreciate you making this article available, the rest of the site is also high quality. Have a fun.
Wow! Thank you! I always wanted to write on my blog something like that. Can I take a portion of your post to my site?
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.
I visited many sites but the audio feature for audio songs existing at
this web site is really wonderful.