1114-Get a Rectangular Field
問題概要
5x5のマス目の情報が与えられる。
中に入る最大の長方形の面積を求めよ。
考え方
ヒストグラムの最大長方形だと見なすことで
蟻本p280の考え方が利用出来る。
ただ、5x5なので普通に全探索しても良いかも。
実装(C++)
#include <iostream> using namespace std; /*ヒストグラムの最大長方形*/ const int MAX_N=5; int n; //ヒストグラムの個数 int h[MAX_N]; //ヒストグラムのデーター long long solve(){ int L[MAX_N],R[MAX_N],st[MAX_N]; //Lの計算 int t=0; for(int i=0;i<n;i++){ while(t>0&&h[st[t-1]]>h[i])t--; L[i]=t==0?0:(st[t-1]+1); st[t++]=i; } //Rの計算 t=0; for(int i=n-1;i>=0;i--){ while(t>0&&h[st[t-1]]>=h[i])t--; R[i]=t==0?n:st[t-1]; st[t++]=i; } long long res=0; for(int i=0;i<n;i++){ res=max(res,(long long)h[i]*(R[i]-L[i])); } return res; } int main() { int M[5][5]; int T; cin>>T; for(;T--;){ for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin>>M[i][j]; int res=0; for(int i=0;i<5;i++){ for(int j=3;j>=0;j--){ if(M[i][j])M[i][j]=M[i][j]+M[i][j+1]; } } for(int i=0;i<5;i++){ n=5; for(int j=0;j<5;j++){ h[j]=M[j][i]; } res=max(res,(int)solve()); } cout<<res<<endl; } return 0; }