网站总浏览量,企业文化ppt模板免费,网站制作的要点和步骤详解,欧米茄官方手表问题描述 试题编号#xff1a;201312-3试题名称#xff1a;最大的矩形时间限制#xff1a;1.0s内存限制#xff1a;256.0MB问题描述#xff1a; 问题描述在横轴上放了n个相邻的矩形#xff0c;每个矩形的宽度是1#xff0c;而第i#xff08;1 ≤ i ≤ n#xff09;个矩…问题描述 试题编号201312-3试题名称最大的矩形时间限制1.0s内存限制256.0MB问题描述 问题描述 在横轴上放了n个相邻的矩形每个矩形的宽度是1而第i1 ≤ i ≤ n个矩形的高度是hi。这n个矩形构成了一个直方图。例如下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。 请找出能放在给定直方图里面积最大的矩形它的边要与坐标轴平行。对于上面给出的例子最大矩形如下图所示的阴影部分面积是10。 输入格式 第一行包含一个整数n即矩形的数量(1 ≤ n ≤ 1000)。 第二行包含n 个整数h1, h2, … , hn相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。 输出格式 输出一行包含一个整数即给定直方图内的最大矩形的面积。 样例输入 63 1 6 5 2 3 样例输出 10 题目大意有n个矩形宽为1给出每个点的高度需要求出最大的矩形的面积。 //猛一看觉得挺难仔细看看觉得还可以一次AC~ #include iostream
#include vector
#include cstdio
using namespace std;
int rec[1001][1001];
int main() {int n;cinn;int maxs0;for(int i0;in;i){cinrec[i][i];if(rec[i][i]maxs)maxsrec[i][i];}for(int i0;in;i){int minsrec[i][i];for(int ji1;jn;j){rec[i][j]min(mins,rec[j][j]);minsrec[i][j];}}int temp0;for(int i0;in;i){for(int ji1;jn;j){//coutrec[i][j] ;temp(j-i1)*rec[i][j];if(tempmaxs)maxstemp;}//cout\n;}coutmaxs;return 0;
} 1.有一个rec矩阵对角线上表示只有当前矩形自己时的面积 2.从第一个依次往后遍历看能达到的最大高度是有最低高度限制的 3.然后再双层循环注意宽度是j-i1而不是j-i这样即可计算出宽*高面积。转载于:https://www.cnblogs.com/BlueBlueSea/p/9612476.html
