北京 @ 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 懂了,感谢!