加强版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;
}