POJ2082 Terrible Sets
2024-08-27 00:31:47
Terrible Sets
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 5067 | Accepted: 2593 |
Description
Let N be the set of all natural numbers {0 , 1 , 2 , . . . }, and R be the set of all real numbers. wi, hi for i = 1 . . . n are some elements in N, and w0 = 0.
Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑0<=j<=i-1wj <= x <= ∑0<=j<=iwj}
Again, define set S = {A| A = WH for some W , H ∈ R+ and
there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈
R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained
in set B}.
Your mission now. What is Max(S)?
Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy.
But for this one, believe me, it's difficult.
Define set B = {< x, y > | x, y ∈ R and there exists an index i > 0 such that 0 <= y <= hi ,∑0<=j<=i-1wj <= x <= ∑0<=j<=iwj}
Again, define set S = {A| A = WH for some W , H ∈ R+ and
there exists x0, y0 in N such that the set T = { < x , y > | x, y ∈
R and x0 <= x <= x0 +W and y0 <= y <= y0 + H} is contained
in set B}.
Your mission now. What is Max(S)?
Wow, it looks like a terrible problem. Problems that appear to be terrible are sometimes actually easy.
But for this one, believe me, it's difficult.
Input
The
input consists of several test cases. For each case, n is given in a
single line, and then followed by n lines, each containing wi and hi
separated by a single space. The last line of the input is an single
integer -1, indicating the end of input. You may assume that 1 <= n
<= 50000 and w1h1+w2h2+...+wnhn < 109.
input consists of several test cases. For each case, n is given in a
single line, and then followed by n lines, each containing wi and hi
separated by a single space. The last line of the input is an single
integer -1, indicating the end of input. You may assume that 1 <= n
<= 50000 and w1h1+w2h2+...+wnhn < 109.
Output
Simply output Max(S) in a single line for each case.
Sample Input
3
1 2
3 4
1 2
3
3 4
1 2
3 4
-1
Sample Output
12
14
Source
【题解】
先看暴力做法
以每一个方块为起点,看他能向右拓展到什么地方,这块面积来更新答案,复杂度n^2
这种东西很套路,就是用单调栈维护。
我们以向左延伸为例
我们不难发现如果突然递减,那么小的那个将制约前面的向右延伸,前面比他高的就等价于与他同高度了
于是弹出来就可以了
答案需要在如下几个地方更新:
1、一整个大方块
2、弹出的时候,累加宽度,乘这个小的高度,表示向左能延伸到什么地方。然后用累加高度和这个笑的高度
虚拟一个新的方块压到栈里面
3、扫完后,把整个栈慢慢弹出,累加宽度更新答案
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define max(a, b) ((a) < (b) ? (b) : (a)) const int MAXN = + ; inline void read(int &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '')c = ch, ch = getchar();
while(ch <= '' && ch >= '')x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} int n,w,h,stackw[MAXN],stackh[MAXN],top,ans; int main()
{
while(scanf("%d", &n) != EOF && n != -)
{
read(stackw[++top]), read(stackh[top]);
ans = stackw[top] * stackh[top];
register int lei = ;
for(register int i = ;i <= n;++ i)
{
read(w), read(h);
ans = max(ans, w * h);
if(h < stackh[top])
{
lei = ;
while(h < stackh[top])
{
lei += stackw[top];
ans = max(ans, lei * stackh[top]);
-- top;
}
stackh[++top] = h;
stackw[top] = lei;
}
stackh[++top] = h;
stackw[top] = w;
}
lei = ;
while(top)
{
lei += stackw[top];
ans = max(ans, lei * stackh[top]);
-- top;
}
printf("%d\n", ans);
}
return ;
}
POJ2082
最新文章
- 探究@property申明对象属性时copy与strong的区别
- 【原】关于Python中setuptools安装的问题
- 使用.net Reflector手动修改单个dll文件
- jsrender for object
- SQL语句调优 - 索引上的数据检索方法
- java开发之多线程需要学习和理解的东西
- Solution for Latex error: ";Cannot determine size of graphic";
- 将CMD内的显示内容输出到txt文件
- android开发之使用上下文菜单
- Java 四种线程池的用法分析
- 使用 jackson序列格式化日期
- 理解LinkedHashMap
- 提取出图像中感兴趣的部分,cvSetImageRoi,Rect
- Arcpy多线程热力图
- <;script>; 属性crossorigin
- Hiho #1075: 开锁魔法III
- USB2.0学习笔记连载(六):USB2.0硬件设计需要注意事项
- 赋诗一首<;<;往事>;>;
- 清除浮动小记,兼容Ie6,7
- python 之 strip()--(转载)
热门文章
- windows 常用的快捷键
- 在sqlserver 的函数或存储过程中抛出异常(raiserror )
- 【DM642学习笔记九】XDS560仿真器 Can&#39;t Initialize Target CPU
- 第三方博客同步xmlrpc、rest、API等相关的文章网址记录
- 2.快速创建springboot项目 连pom文件里面的配置都不用配了
- sql 书写顺序
- 忘记sql server 2008 sa的密码的解决方案
- 教你用webpack搭一个vue脚手架[超详细讲解和注释!](转载)
- 技术人自己的KPI
- JavaScript的坑,缺陷