1506题意：给你连续的直方图（底边边长为1），求连续的矩阵面积。
对每个直方图，分别向左向右进行扩展。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define N 100010 #define mol 1000000007 int i,n,t; LL a[N],l[N],r[N],Max; int main() { while (scanf("%d",&n) && n) { for (i=1; i<=n; ++i) scanf("%I64d",&a[i]); l[1]=1; r[n]=n; for(i=2;i<=n;i++) { t=i; while(t>1&&a[i]<=a[t-1])//从左往右向左扩展 t=l[t-1]; l[i]=t; } for(i=n-1;i>=1;i--) { t=i; while(t Max) Max=(r[i]-l[i]+1)*a[i]; } printf("%I64d\n",Max); } return 0; }
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define maxn 1001 #define mol 1000000007 int t,n,m,a[maxn][maxn],l[maxn][maxn],r[maxn][maxn]; char s[maxn]; int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int i,j; memset(a,0,sizeof(a)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%s",s); if(s[0]=='F') a[i][j]=a[i-1][j]+1; else a[i][j]=0; } } //printf("\n"); int ans=0; for(i=1;i<=n;i++) { int t; l[i][1]=1;r[i][m]=m; for(j=2;j<=m;j++) { t=j; while(t>1&&a[i][j]<=a[i][t-1]) t=l[i][t-1]; l[i][j]=t; } for(j=m-1;j>0;j--) { t=j; while(t ans) ans=a[i][j]*(r[i][j]-l[i][j]+1); } } printf("%d\n",ans*3); } return 0; } /* 2 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F 5 5 R R R R R R R R R R R R R R R R R R R R R R R R R */
