// l表示从l[i]到i连续大于a[i]的最远左区间。r表示从i到r[i]连续大于a[i]的最远又区间
DP 找出 a[i] 的最远左区间和最远右区间与自己连着的比自己大的数的长度 , 然后用这个长度乘以 a[i], 乘积最大的那个就是答案
hdoj 1506
#includehdoj 1505是1506的加强版，对于矩阵的每一行採取相同的操作#include #include using namespace std;#define N 100000+10#define INF 0xfffffff#define ll __int64ll 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;}
#include#include #include using namespace std;#define N 1000+10char 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;}