60求调
查看原帖
60求调
1066617
_ACGODs_楼主2024/11/25 22:12
#include<bits/stdc++.h>
using namespace std;
int a[2010][2010]={};
int Left[2010][2010]={};
int up[2010][2010]={};//往上繁衍的次数。
int dp[2010][2010]={};
int Leftdp[2010][2010]={};
int n,m;
int maxs,maxr;
//显然昨天的贪心并不是最优解
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			Left[i][j]=up[i][j]=dp[i][j]=1;
			Leftdp[i][j]=a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=2;j<=m;j++){
			if(a[i][j]!=a[i][j-1]) Left[i][j]=Left[i][j-1]+1;
			else Left[i][j]=1;
			Leftdp[i][j]=Left[i][j];
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]!=a[i-1][j]){//还有选择余地
				up[i][j]=up[i-1][j]+1,
				Leftdp[i][j]=min(Leftdp[i-1][j],Left[i][j]),
				dp[i][j]=up[i][j]*Leftdp[i][j],
				maxr=max(maxr,dp[i][j]),
				maxs=max(maxs,min(up[i][j],Leftdp[i][j])*min(up[i][j],Leftdp[i][j]));			
				if(dp[i][j]<Left[i][j]) dp[i][j]=Leftdp[i][j]=Left[i][j],up[i][j]=1;
			}else dp[i][j]=Leftdp[i][j]=Left[i][j],up[i][j]=1;
		}
	}
//	cout<<"Left:"<<endl;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<Left[i][j]<<' ';
//		}cout<<endl;
//	}cout<<endl;
//	cout<<"Leftdp:"<<endl;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<Leftdp[i][j]<<' ';
//		}cout<<endl;
//	}cout<<endl;
//	cout<<"Up:"<<endl;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<up[i][j]<<' ';
//		}cout<<endl;
//	}cout<<endl;
//	cout<<"Dp:"<<endl;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<dp[i][j]<<' ';
//		}cout<<endl;
//	}cout<<endl;
	cout<<maxs<<endl<<maxr<<endl;
	return 0;
}
2024/11/25 22:12
加载中...