1506题目
1505题目
1506：
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int Max = 100010;
int main()
{
int n;
long long num[Max],temp;
int L[Max],R[Max];
while(~scanf("%d",&n),n)
{
memset(L,0,sizeof( L));
memset(R,0,sizeof(R));
for(int i=1; i<=n; i++)
scanf("%lld",&num[i]);
L[1] = 1;
R[n] = n;
for(int i=2; i<=n; i++)
{
temp = i;
while( temp > 1 && num[i]<=num[temp-1])
temp = L[temp-1];
L[i] = temp;
}
for(int i=n-1; i>=1; i--)
{
temp = i;
while(temp < n && num[i] <= num[temp+1])
temp = R[temp+1];
R[i] = temp ;
}
long long max = 0;
for(int i=1; i<= n; i++)
{
if((R[i]-L[i]+1)*num[i] > max ) max = (R[i]-L[i]+1)*num[i];
}
printf("%lld\n",max);
}
return 0;
}1505：
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int d[1010][1010],L[1010],R[1010];
int main()
{
int n,T,m;
char ch[2];
cin>>T;
while(T--)
{
memset(d,0,sizeof(d));
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m; j++)
{
cin>>ch;
if(ch[0]=='F')
d[i][j]=d[i-1][j] + 1;
else
d[i][j] = 0;
}
}
int max = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<= m; j++ )
{
L[j] = j;
while(L[j]>1 && d[i][j] <= d[i][L[j]-1] )
L[j] = L[ L[j] - 1 ];
}
for(int j=m; j>=1; j--)
{
R[j] = j;
while(R[j] < m && d[i][j] <= d[i][R[j] + 1]){
R[j] = R[ R[j] + 1];
}
}
for(int j=1; j<=m; j++)
{
if(max < ((R[j]-L[j]+1)*d[i][j]))
max = ( R[j]-L[j]+1)*d[i][j];
}
}
cout<<max*3 <<endl;
}
return 0;
}
这两道题差不多，第一道题相对于第二道来说是一维的，第二道相对于第一道来说是二维的。
左边向左延伸，右边向右延伸，直至能够延伸到的最大距离。