上一篇博客中提到了用O（n）的復雜度求矩形的最大面積，這里遍歷每一行把每一行及其以上部分當作排列的矩形這樣就可以求出最大的矩形面積了。

/*
ID:jinbo wu
TASK: rectbarn
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
int a[3010];
bool vis[3010][3010];
int main()
{freopen("rectbarn.in","r",stdin);freopen("rectbarn.out","w",stdout);int x,y;ios::sync_with_stdio(false);int n,m,k;cin>>n>>m>>k;int ans=0;for(int i=1;i<=k;i++){cin>>x>>y;vis[x][y]=1;}a[m+1]=-1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!vis[i][j])a[j]=a[j]+1;else a[j]=0;}stack<int> s;int j=1;while(j<=m+1){if(s.size()==0||a[j]>a[s.top()])s.push(j++);else{int t=s.top();s.pop();int h;if(s.size()==0)h=a[t]*(j-1);else h=a[t]*(j-s.top()-1);ans=max(h,ans);}}}cout<<ans<<endl;}

總結

以上是生活随笔為你收集整理的A Rectangular Barn的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。