求助!结果少了1,错在哪里?

P1736 创意吃鱼法

北京 @ 2021-03-20 22:22:25

评测详情

#4

正确输出:5

我的程序输出:4

debug一晚上也没有发现错误,请求帮助

感谢指教!

以下是代码:

//P1736 创意吃鱼法
#include<bits/stdc++.h>
using namespace std;
bool a[2500+10][2500+10];
long long dp1[2500+10][2500+10],dp2[2500+10][2500+10],ans;
int main()
{
    //freopen("P1736_4.in","r",stdin);
    int n,m;
    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]==1)
            {
                dp1[i][j]=1;
                bool flag=0;
                if(dp1[i-1][j-1])
                {
                    int k=j-1,l=i-1,kk=1,ll=1;
                    for(int k=j-1,kk=1;kk<=dp1[i-1][j-1];++kk,--k)
                        if(a[i][k]==1){flag=1;break;}
                    for(int l=i-1,ll=1;ll<=dp1[i-1][j-1];++ll,--l)
                        if(a[l][j]==1){flag=1;break;}
                    if(flag)
                        {dp1[i][j]=min(ll,kk);continue;}
                    else dp1[i][j]=dp1[i-1][j-1]+1;
                }
                ans=max(ans,dp1[i][j]);
            }
        }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            if(a[i][j]==1)
            {
                dp2[i][j]=1;
                bool flag=0;
                if(dp2[i-1][j+1])
                {
                    int k=j-1,l=i-1,kk=1,ll=1;
                    for(k=j+1,kk=1;kk<=dp2[i-1][j+1];++kk,++k)
                        if(a[i][k]==1){flag=1;break;}
                    for(l=i-1,ll=1;ll<=dp2[i-1][j+1];++ll,--l)
                        if(a[l][j]==1){flag=1;break;}
                    if(flag)
                        {dp2[i][j]=min(ll,kk);continue;}
                    else dp2[i][j]=dp2[i-1][j+1]+1;
                }
                ans=max(ans,dp2[i][j]);
            }
        }

    cout<<ans;
    return 0;
}

by 北京 @ 2021-03-20 22:25:01

朴素做法,dp1[i][j]表示以(i,j)为正方形右下角的最优解,dp2[i][j]表示以(i,j)为正方形左下角的最优解


by Jr_Zlw @ 2021-03-21 07:33:53

@北京 你的ll和kk在for循环里面是新定义的吧,外面一层循环的变量好像是不会改变的。(上面一层循环)


by Jr_Zlw @ 2021-03-21 07:35:05

建议打多一个dp预处理0的个数存起来(更快一点


by 北京 @ 2021-03-21 09:50:48

@Jr_zLiwen 懂了,感谢!


|