Lance1ot @ 2018-01-30 09:50:21
求解?
答案:5
我的输出:4
#include<iostream>
#include<cstdio>
using namespace std;
int dp[2501][2501][2];
long long map[2501][2501];
int main()
{
//cin.sync_with_stdio(false);
int n,m;
//cin>>n>>m;
scanf("%d %d",&n,&m);
int maxn=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
//cin>>map[i][j];
scanf("%d",&map[i][j]);
if(map[i][j])
{
dp[i][j][0]++;
dp[i][j][1]++;
maxn=1;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
map[i][j]=map[i][j]-map[i-1][j-1]+map[i-1][j]+map[i][j-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(dp[i][j][0]&&dp[i][j][1])
{
if(dp[i-1][j-1][0])
{
int &x=dp[i-1][j-1][0];
if(map[i][j]+map[i-1][j-x-1]-map[i-1][j]-map[i][j-x-1]-1==0&&map[i][j]-map[i-x-1][j]-map[i][j-1]+map[i-x-1][j-1]-1==0)
dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-1][0]+1);
}
if(dp[i-1][j+1][1])
{
int &x=dp[i-1][j+1][1];
if(map[i][j]-map[i-x-1][j]-map[i][j-1]+map[i-x-1][j-1]-1==0&&map[i][j+x]-map[i][j-1]-map[i-1][j+x]+map[i-1][j-1]-1==0)
dp[i][j][1]=max(dp[i][j][1],dp[i-1][j+1][1]+1);
}
maxn=max(maxn,dp[i][j][1]);
maxn=max(maxn,dp[i][j][0]);
}
}
cout<<maxn;
}