最大の矩形(テスト全対、なぜ20点しかないのですか?)
1119 ワード
問題の説明
横軸にはn個の隣接する矩形が配置され,各矩形の幅は1であり,i番目の(1≦i≦n)個の矩形の高さはhiであった.このn個の矩形はヒストグラムを構成する.例えば、下図の6つの矩形の高さは、それぞれ3,1,6,5,2,3である.
指定したヒストグラムに配置できる面積が最も大きい矩形を見つけてください.その辺は座標軸と平行になります.上記の例では、最大矩形の下図のような影の部分の面積は10である.
入力フォーマット
第1行は、整数n、すなわち矩形の数(1≦n≦1000)を含む.
2行目は、n個の整数h 1,h 2,...,hnを含み、隣接する数の間にスペースで区切られている.(1 ≤ hi ≤ 10000).hiはi番目の矩形の高さです.
出力フォーマット
与えられたヒストグラム内の最大矩形の面積である整数を含む行を出力します.
サンプル入力
6
3 1 6 5 2 3
サンプル出力
10
横軸にはn個の隣接する矩形が配置され,各矩形の幅は1であり,i番目の(1≦i≦n)個の矩形の高さはhiであった.このn個の矩形はヒストグラムを構成する.例えば、下図の6つの矩形の高さは、それぞれ3,1,6,5,2,3である.
指定したヒストグラムに配置できる面積が最も大きい矩形を見つけてください.その辺は座標軸と平行になります.上記の例では、最大矩形の下図のような影の部分の面積は10である.
入力フォーマット
第1行は、整数n、すなわち矩形の数(1≦n≦1000)を含む.
2行目は、n個の整数h 1,h 2,...,hnを含み、隣接する数の間にスペースで区切られている.(1 ≤ hi ≤ 10000).hiはi番目の矩形の高さです.
出力フォーマット
与えられたヒストグラム内の最大矩形の面積である整数を含む行を出力します.
サンプル入力
6
3 1 6 5 2 3
サンプル出力
10
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n,sum=0;
cin>>n;
vector<int>a;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a.push_back(x);
}
for(int j=2;j<=n;j++)
for(int k=0;k<n-(j-1);k++)
{
vector<int> b;
int h=0,m=k;
while(h<j)
{
b.push_back(a[m]);
h++;
m++;
}
int min0=*min_element(b.begin(),b.end());
int sum0=min0*j;
if(sum0>sum)
sum=sum0;
}
cout<<sum<<endl;
return 0;
}