題目連結: https://tioj.ck.tp.edu.tw/problems/1470
# 內容
一塊 N*M 單位方格大小的區域中，每一單位都有一個高度。
請你找一塊面積最大的矩形子區域，使得這一個區域中的任一格，其左方 (若在該區域中) 以及上方 (若在該區域中) 的高度皆小於該格的高度。
# 思路
跟這題有些許神似 (不只些許 ，只不過呢... 這次還需要再多判斷上方的狀況，所以，重新寫了一遍
用 DP 將每點最大的高給記錄下來，再用另一個陣列將同寬記錄下來，之後，就跟那題一樣暴力搜索一下就行了
要記得找到最大的高時，還是要檢查對應其高的兩端點是否在同邊喔！！
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
#define MAXN 100 | |
ll a[MAXN][MAXN] ; | |
int main(){ | |
int N ,M ; | |
while (cin>>N>>M){ | |
//input ------------- | |
for (int i=0 ;i<N ;i++ ) | |
for (int j=0 ;j<M ;j++ ) | |
cin>>a[i][j]; | |
//dp Height---------------- | |
ll H[MAXN][MAXN] ; | |
for (int i=0 ;i<M ;i++ ){ | |
H[0][i]=1 ; | |
for (int j=1 ;j<N ;j++ ){ | |
if (a[j][i]>a[j-1][i]) H[j][i]=H[j-1][i]+1 ; | |
else H[j][i]=1 ; | |
} | |
} | |
//differentiate----------------------- | |
ll W[MAXN][MAXN] ; | |
for (int i=0 ;i<N ;i++ ){ | |
W[i][0]=0 ; | |
for (int j=1 ;j<M ;j++ ) | |
if (a[i][j]>a[i][j-1]) W[i][j]=W[i][j-1] ; | |
else W[i][j]=W[i][j-1]+1 ; | |
} | |
ll ans=0 ; | |
for (int i=0 ;i<N ;i++ ){ //column | |
for (int l=0 ;l<M ;l++ ){ //left side | |
for (int r=l;r<M && W[i][r]==W[i][l] ;r++ ){ //right side | |
ll h = 1000; | |
for (int k=l ;k<=r ;k++ ) h=min(h,H[i][k]) ;//find height | |
for (int k=1 ;k<=h ;k++ ) //check | |
if (W[i-k+1][l]!=W[i-k+1][r]){ | |
h=k-1; break; | |
} | |
ans=max(ans,h*(r-l+1)) ; | |
} | |
} | |
} | |
cout<<ans<<endl; | |
} | |
} |
