求解

P1736 创意吃鱼法

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;
}

|