经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
cf1060E. Sergey and Subway(思维 枚举)
来源:cnblogs  作者:自为风月马前卒  时间:2018/12/7 9:33:19  对本文有异议

题意

题目链接

Sol

好好读题 => 送分题

不好好读题 => 送命题

开始想了\(30\)min数据结构发现根本不会做,重新读了一遍题发现是个傻逼题。。。

\(C_{i, j} = a[i] * b[j]\)

根据乘法分配律,题目就变成了在数组\(a, b\)中分别选一段连续的区间,要求权值和相乘\(<= X\),最大化区间长度乘积

\(n^2\)模拟一下即可

  1. #include<bits/stdc++.h>
  2. #define Pair pair<int, int>
  3. #define MP(x, y) make_pair(x, y)
  4. #define fi first
  5. #define se second
  6. #define int long long
  7. #define LL long long
  8. #define rg register
  9. #define pt(x) printf("%d ", x);
  10. #define Fin(x) {freopen(#x".in","r",stdin);}
  11. #define Fout(x) {freopen(#x".out","w",stdout);}
  12. #define chmin(x, y) (x = x < y ? x : y)
  13. using namespace std;
  14. const int MAXN = 2001, INF = 1e18 + 10, mod = 1e9 + 7;
  15. const double eps = 1e-9;
  16. inline int read() {
  17. char c = getchar(); int x = 0, f = 1;
  18. while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
  19. while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  20. return x * f;
  21. }
  22. int N, M, a[MAXN], b[MAXN], f[MAXN], g[MAXN], Lim, ans;
  23. main() {
  24. N = read(); M = read();
  25. for(int i = 1; i <= N; i++) a[i] = read();
  26. for(int i = 1; i <= M; i++) b[i] = read();
  27. memset(f, 0x7f, sizeof(f));
  28. memset(g, 0x7f, sizeof(g));
  29. Lim = read();
  30. for(int i = 1; i <= N; i++) {
  31. int mn = 0;
  32. for(int j = i; j <= N; j++) mn += a[j], chmin(f[j - i + 1], mn);
  33. }
  34. for(int i = 1; i <= M; i++) {
  35. int mn = 0;
  36. for(int j = i; j <= M; j++) mn += b[j], chmin(g[j - i + 1], mn);
  37. }
  38. for(int i = 1; i <= N; i++) {
  39. for(int j = 1; j <= M; j++) {
  40. if(f[i] * g[j] <= Lim)
  41. ans = max(ans, j * i);
  42. }
  43. }
  44. cout << ans;
  45. return 0;
  46. }
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号