CCF201312-3 最大的矩形

68 阅读 0 评论 45 点赞

我是靠谱客的博主单薄超短裙，最近开发中收集的这篇文章主要介绍CCF201312-3 最大的矩形，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入代码片#include<iostream>
using namespace std;
/*采用从左向右遍历的方法，半暴力求解
求出包含从第i个到第j个的矩形的组合矩形的面积*/
int main(){
int n;
cin>>n;
int h[n];//存放每个矩形高度
long int k=0;
for(int i=0;i<n;i++) cin>>h[i];
long int s;
for(int i=0;i<n;i++){
int l=1e5;
for(int j=i;j<n;j++){
if(h[j]<l) l=h[j];
s=l*(j-i+1);
if(s>k) k=s;
}
}
cout<<k;
}

注意点：1.虽然题目说了高度不超过10000，但是定义l=1e4时会有一个测试点不得分。没弄清楚为什么。
2.当初试图定义一个数组s[n][n]用来保存每个面积。结果会使得空间使用超标，只能拿40分。实际上定义二维数组多此一举。