90分玄学求调
查看原帖
90分玄学求调
726089
Ecesq_4楼主2024/8/7 16:23

加强版P1169过的代码删了删来交这题,结果Wa第5个点没过??

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,ans1,ans2;
struct node
{
	int x;
	int y;
	int dx;
}dp[2010][2010];
bool dt[2010][2010];
void dmax(int x,int y)
{ 
	ans2=max(ans2,dp[x][y].dx);
	if(dp[x][y].x==dp[x][y].y)
	{
		ans1=max(ans1,dp[x][y].x);
	}
} 
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>dt[i][j];
		}
	}
	dp[1][1]=node{1,1,1};
	dmax(1,1);
	for(int i=2;i<=n;i++)
	{
		if(dt[i][1]==dt[i-1][1])
		{
			dp[i][1]=node{1,1,1};
		}	
		else 
		{
			dp[i][1]=node{dp[i-1][1].x+1,1,dp[i-1][1].x+1}; 
		}
		dmax(i,1); 
	}
	for(int i=2;i<=m;i++)
	{
		if(dt[1][i]==dt[1][i-1])
		{
			dp[1][i]=node{1,1,1};
		}	
		else 
		{
			dp[1][i]=node{1,dp[1][i-1].y+1,dp[1][i-1].y+1};
		} 
		dmax(1,i); 
	} 
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=m;j++)
		{
			if(dt[i][j]==dt[i-1][j])
			{
				if(dt[i][j]==dt[i][j-1])
				{
					dp[i][j]=node{1,1,1};
				}  
				else 
				{
					dp[i][j]=node{1,dp[i][j-1].y+1,dp[i][j-1].y+1};
				}
			} 
			else 
			{
				if(dt[i][j]==dt[i][j-1])
				{
					dp[i][j]=node{dp[i-1][j].x+1,1,dp[i-1][j].x+1};
				}
				else if(dp[i][j-1].x<dp[i-1][j].x+1 && dp[i-1][j].y<dp[i][j-1].y+1)
				{
					node w,e;
					w=node{dp[i-1][j].x+1,dp[i-1][j].y,(dp[i-1][j].x+1)*(dp[i-1][j].y)};
					e=node{dp[i][j-1].x,dp[i][j-1].y+1,(dp[i][j-1].x)*(dp[i][j-1].y+1)};
					if(w.dx>e.dx) dp[i][j]=w;
					else dp[i][j]=e;
				}
				else 
				{
					dp[i][j]=node{dp[i-1][j].x+1,dp[i][j-1].y+1,(dp[i-1][j].x+1)*(dp[i][j-1].y+1)};
				}
			} 
			dmax(i,j);
		}
	}
	cout<<ans1<<endl;
	return 0;
}
2024/8/7 16:23
加载中...