// l表示从l[i]到i连续大于a[i]的最远左区间。r表示从i到r[i]连续大于a[i]的最远又区间
DP 找出 a[i] 的最远左区间和最远右区间与自己连着的比自己大的数的长度 , 然后用这个长度乘以 a[i], 乘积最大的那个就是答案
hdoj 1506
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100000+10
#define INF 0xfffffff
#define ll __int64
ll Max(ll x,ll y)
{
if(x>y)
return x;
return y;
}
ll r[N],l[N];
ll a[N];
int main()
{
ll n;
while(scanf("%I64d",&n),n)
{
for(int i=1;i<=n;i++)
scanf("%I64d",&a[i]);
a[0]=a[n+1]=-INF;
l[0]=r[n+1]=0;
for(int i=1;i<=n;i++)
{ l[i]=i;
while(a[l[i]-1]>=a[i])
l[i]=l[l[i]-1]; }
for(int i=n;i>=1;i--)
{ r[i]=i;
while(a[r[i]+1]>=a[i])
r[i]=r[r[i]+1]; }
ll maxn=0;
for(int i=1;i<=n;i++)
{
maxn=Max((r[i]-l[i]+1)*a[i],maxn);
}
printf("%I64d\n",maxn);
}
return 0;
}
hdoj 1505是1506的加强版，对于矩阵的每一行採取相同的操作
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1000+10
char a[N][N];
int dp[N][N];
int r[N],l[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
int maxn=0;
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(" %c",&a[i][j]);
if(a[i][j]=='R')
dp[i][j]=0;
else
dp[i][j]=dp[i-1][j]+1;
}
} for(int i=1;i<=n;i++)
{
dp[i][0]=dp[i][m+1]=-1;
l[0]=r[m+1]=0;
for(int j=1;j<=m;j++)
{
l[j]=j;
while(dp[i][l[j]-1]>=dp[i][j])
l[j]=l[l[j]-1];
}
for(int j=m;j>=1;j--)
{ r[j]=j;
while(dp[i][r[j]+1]>=dp[i][j])
r[j]=r[r[j]+1]; }
for(int j=1;j<=m;j++)
{
maxn=max(maxn,(r[j]-l[j]+1)*3*dp[i][j]);
} }
printf("%d\n",maxn);
}
return 0;
}