当前位置：网站首页>51nod 1102 面积最大的矩形

51nod 1102 面积最大的矩形

2022-07-15 11:44:00 【51CTO】

题目链接：这里写链接内容
dp题，面积为一个矩形的左扩展和右扩展边界乘上这个矩形的高度
代码如下：

       
       #include<cstdio>
       
#include<iostream>
       
#include<algorithm>
       
#include<cstring>
       
using namespace std;
       
#define N 50010
       
long long int a[N],l[N],r[N];
       
int main(){
       
    int i,j,n,m;
       
    cin>>n;
       
    for(i=1;i<=n;i++){
       
        cin>>a[i];
       
        l[i]=r[i]=i;
       
    }
       
    a[n+1]=a[0]=0;
       
    for(i=1;i<=n;i++){
       
            j=i+1;
       
        while(a[i]<=a[j]) {
       
            j++;
       
        }
       
        r[i]=j;
       
    }
       
    for(i=1;i<=n;i++){
       
        j=i-1;
       
        while(a[i]<=a[j]) {
       
            j--;
       
        }
       
        l[i]=j;
       
    }
       
   // for(i=1;i<=n;i++) cout<<l[i]<<r[i]<<endl;
       
    long long int Max=0;
       
    for(i=1;i<=n;i++){
       
        Max=max(Max,a[i]*(r[i]-l[i]-1));
       
    }
       
    cout<<Max<<endl;
       
    return 0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15719342/5475074

当前位置：网站首页>51nod 1102 面积最大的矩形

51nod 1102 面积最大的矩形

边栏推荐

猜你喜欢

随机推荐