首页 > 代码库 > HDU 1505 Largest Rectangle in a Histogram && HDU 1506 City Game(动态规划)
HDU 1505 Largest Rectangle in a Histogram && HDU 1506 City Game(动态规划)
1506题意:给你连续的直方图(底边边长为1),求连续的矩阵面积。
对每个直方图,分别向左向右进行扩展。
#include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<map> #include<cmath> #include<iostream> #include <queue> #include <stack> #include<algorithm> #include<set> 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<n&&a[i]<=a[t+1])//从右往左向右扩展 t=r[t+1]; r[i]=t; } Max=0; for (i=1; i<=n; ++i) { if ((r[i]-l[i]+1)*a[i]>Max) Max=(r[i]-l[i]+1)*a[i]; } printf("%I64d\n",Max); } return 0; }
#include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<map> #include<cmath> #include<iostream> #include <queue> #include <stack> #include<algorithm> #include<set> 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<m&&a[i][j]<=a[i][t+1]) t=r[i][t+1]; r[i][j]=t; } for(j=1;j<=m;j++) { if(a[i][j]*(r[i][j]-l[i][j]+1)>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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。