网站建设的背景有哪些,asp最新版本,安徽苏亚建设安装有限公司网站,西安市建网站找哪家【题目描述】#xff1a; 地面上从左到右并排紧挨着摆放多个矩形#xff0c;已知这此矩形的底边宽度都为1#xff0c;高度不完全相等。求在这些矩形包括的范围内能得到的面积最大的矩形#xff0c;打印出该面积。所求矩形可以横跨多个矩形#xff0c;但不能超出原有矩形所…【题目描述】 地面上从左到右并排紧挨着摆放多个矩形已知这此矩形的底边宽度都为1高度不完全相等。求在这些矩形包括的范围内能得到的面积最大的矩形打印出该面积。所求矩形可以横跨多个矩形但不能超出原有矩形所确定的范围。 如 n 7, 序列为2 1 4 5 1 3 3 _ _ _ | | _ | | | || | _ _ |H||H| _ _ _ | || | | || | _ |H||H| | || |
| | _ | || | _ | || | | | _ |H||H| _ | || |
|_||_||_||_||_||_||_| |_||_||H||H||_||_||_| 最大面积8 【输入描述】 输入有多组数据每组数据一行 第一个数N表示矩形个数 后面跟N个正整数第i个正整数hi表示第i个矩形的高度。 最后一行以一个单独的0结束。 【输出描述】 每组输入数据一行一个数表示最大矩形面积。 【样例输入】 7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0 【样例输出】 8
4000 【时间限制、数据范围及描述】 时间1s 空间64M 30 %: 1N100 60 %: 1N1,000 100%: 1N500,0000hi1,000,000,000 题解问题可简化为两个子问题每找到一个点查找左第一个比他大的右边第一个比她大的。 这里用单调栈即可两坐标之差再乘上i的高度即可得出答案。 #include iostream
#include cstdio
#include cstring
#define MAX_N 500005
using namespace std;int main()
{int n;while(~scanf(%d,n)n){int a[MAX_N];int l[MAX_N],r[MAX_N];for(int i1;in;i)scanf(%d,a[i]);l[0]0,l[n1]0;for(int i1;in;i){int ki-1;if(a[i]a[k]){while(k0a[i]a[k]) kl[k]-1; }l[i]k1;}for(int in;i1;i--){int ki1;if(a[i]a[k]){while(kn1a[i]a[k]) kr[k]1;}r[i]k-1;}long long maxn-1;for(int i1;in;i){long long s(long long)(r[i]-l[i]1)*a[i];if(smaxn) maxns;}printf(%lld\n,maxn);}return 0;
} 转载于:https://www.cnblogs.com/wuhu-JJJ/p/11205744.html
