1 条题解

  • 0
    @ 2026-4-13 11:50:00
    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int a[2001][2001];
    int b[2001][2001];
    int ans;
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cin>>a[i][j];
    		}
    	}
    	for(int i=1;i<=n;i++){
    		int m=0;
    		for(int j=1;j<=n;j++){
    			if(a[i][j]==0){
    				m++;
    				
    			}
    			else{
    				m=0;
    			}
    			b[i][j]=m;//存左边有多少个连续的零 
    		}
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			int p=b[i][j];
    			if(p==0){
    				continue;
    			}
    			ans=max(p,ans);
    			for(int k=i+1;k<=n;k++){
    				p=min(p,b[k][j]);
    				if(p==0||p*(n-i+1)<=ans){//最优性剪枝 
    					break;
    				}
    				ans=max(p*(k-i+1),ans);
    			}
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    
    
    • 1

    *【栈:单调栈】[POI 2002] 最大的园地

    信息

    ID
    4640
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    5
    已通过
    2
    上传者