站外求助!!!
查看原帖
站外求助!!!
1111160
starish楼主2024/8/28 15:39
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,ans1,ans2;
int lie[2005][2005],hang[2005][2005];
//单列第ij点向上的最大长度,使得条件成立
//单行第ij点向下的最大长度,使得条件成立
struct{
	int x,y;
}dp[2005][2005];
bool a[2005][2005];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cin>>a[i][j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]!=a[i-1][j])lie[i][j]=lie[i-1][j]+1;
			else lie[i][j]=1;
			if(a[i][j]!=a[i][j-1])hang[i][j]=hang[i][j-1]+1;
			else hang[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++)dp[i][1].x=lie[i][1],dp[i][1].y=1;
	for(int i=1;i<=m;i++)dp[1][i].y=hang[1][i],dp[1][i].x=1;
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			if(a[i-1][j-1]==a[i][j]&&a[i][j]!=a[i-1][j]&&a[i][j]!=a[i][j-1]){
				dp[i][j].x=min(dp[i-1][j-1].x,lie[i-1][j])+1;
				dp[i][j].y=min(dp[i-1][j-1].y,hang[i][j-1])+1;
			}
			if(dp[i][j].x*dp[i][j].y<lie[i][j]){
				dp[i][j].x=lie[i][j];
				dp[i][j].y=1;
			}
			if(dp[i][j].x*dp[i][j].y<hang[i][j]){
				dp[i][j].y=hang[i][j];
				dp[i][j].x=1;
			}
			ans2=max(ans2,dp[i][j].x*dp[i][j].y);
			if(dp[i][j].x==dp[i][j].y)ans1=max(ans1,dp[i][j].x*dp[i][j].y);
		}
	}
	cout<<ans1<<endl<<ans2;
	return 0;
} 

luogu ac,牛客 80分,why? 玄关

2024/8/28 15:39
加载中...