开闸放水 @ 2017-06-16 21:12:55
错一个点……求高人指教……
思路就是对每个格子每次检查一下那一行那一列的正方形是不是都是空的，是的话那个点的对角线最大值就加上上一行的点的值
f[0][i][j]是左上右下对角线的最大值……f[1][i][j]就是右上左下了
#include <iostream>
#include <string.h>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int min(int a,int b,int c,int d)
{
return min(min(a,b),min(c,d));
}
int max(int a,int b,int c)
{
return max(max(a,b),c);
}
int n,m,a[2501][2501],f[2][2502][2502],ans=0;//f[0][i][j] is the top-left diagonal
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j])
{
f[0][i][j]=f[1][i][j]=1;
int flag0=1,flag1=1;
for(int k=1;k<=f[0][i-1][j-1];k++)
if(a[i][j-k]||a[i-k][j])
flag0=0;
for(int k=1;k<=f[1][i-1][j+1];k++)
if(a[i][j+k]||a[i-k][j])
flag1=0;
if(flag0>0)
f[0][i][j]+=f[0][i-1][j-1];
if(flag1>0)
f[1][i][j]+=f[1][i-1][j+1];
ans=max(ans,f[0][i][j],f[1][i][j]);
}
printf("%d\n",ans);
}
by 梦回还 @ 2017-06-29 09:48:12
我也错了一个点想不明白，答案就差一
#include <cstdio>
#define max(a,b) a>b?a:b
using namespace std;
int n,m,a[2505][2505],d[2505][2505],p[2505][2505],ma;
inline bool check(int x,int y)
{
int k=d[x-1][y-1];
for(int l=x-k;l<x;l++)
if(a[l][y]==1) return false;
for(int q=y-k;q<y;q++)
if(a[x][q]==1) return false;
return true;
}
inline bool find(int x,int y)
{
int k=p[x-1][y+1];
for(int l=x-k;l<x;l++)
if(a[l][y]==1) return false;
for(int q=y+1;q<=y+k;q++)
if(a[x][q]==1) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
ma=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]==0) d[i][j]=0;
else
{
if(a[i-1][j-1]==1&&check(i,j))
{
d[i][j]=d[i-1][j-1]+1;
}
else d[i][j]=1;
}
ma=max(ma,d[i][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]==0) p[i][j]=0;
else
{
if(a[i-1][j+1]==1&&find(i,j))
{
p[i][j]=p[i-1][j+1]+1;
}
else p[i][j]=1;
}
ma=max(ma,p[i][j]);
}
printf("%d",ma);
return 0;
}by void_zxh @ 2017-08-16 16:02:44
真巧，我也一样。。。。。
·
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
while(c<='9'&&c>='0'){x=x*10+c-48;c=getchar();}
return x*f;
}
int n,m;
struct point
{
int v,pre,hi;
}a[2505][2505];
struct line
{
int h,l;
}li[2505][2505];
int main()
{
freopen("dp.in","r",stdin);
freopen("dp.out","w",stdout);
int i,j;
n=read(); m=read();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
a[i][j].v=read();
a[i][j].pre=j;
a[i][j].hi=i;
}
for(i=1;i<=n;i++)
for(j=2;j<=m;j++)
if(a[i][j-1].v==0)
a[i][j].pre=a[i][j-1].pre;
for(j=1;j<=m;j++)
for(i=2;i<=n;i++)
if(a[i-1][j].v==0)
a[i][j].hi=a[i-1][j].hi;
int ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j].v==1)
{
li[i][j].h=min(i-a[i][j].hi+1,j-a[i][j].pre+1);
li[i][j].l=1;
ans=1;
}
for(i=2;i<=n;i++)
for(j=2;j<=m;j++)
if(a[i][j].v==a[i-1][j-1].v&&a[i][j].v==1&&li[i][j].h>=li[i-1][j-1].l+1)
{
li[i][j].h=li[i-1][j-1].l+1;
li[i][j].l+=li[i-1][j-1].l;
ans=max(ans,li[i][j].l);
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
a[i][j].pre=j;
a[i][j].hi=i;
}
for(i=1;i<=n;i++)
for(j=m-1;j>=1;j--)
if(a[i][j+1].v==0)
a[i][j].pre=a[i][j+1].pre;
for(j=1;j<=m;j++)
for(i=2;i<=n;i++)
if(a[i-1][j].v==0)
a[i][j].hi=a[i-1][j].hi;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j].v==1)
{
li[i][j].h=min(i-a[i][j].hi+1,a[i][j].pre-j+1);
li[i][j].l=1;
ans=max(ans,1);
}
for(i=2;i<=n;i++)
for(j=m-1;j>=1;j--)
if(a[i][j].v==a[i-1][j+1].v&&a[i][j].v==1&&li[i][j].h>=li[i-1][j+1].l+1)
{
li[i][j].h=li[i-1][j+1].l+1;
li[i][j].l+=li[i-1][j+1].l;
ans=max(ans,li[i][j].l);
}
printf("%d\n",ans);
return 0;
}
·by Mr_Spade @ 2017-09-06 18:35:49
发现很多人都有这个问题(包括我),现在我想明白是为什么了,在这里统一回复一下.
有这个问题对应的结果应该是WA#4
比如下面这个例子:
6 6 1 1 0 0 0 1
0 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 1
1 0 0 0 0 0
WA#4的代码应该是输出了4,但正确答案是5
这个情况,在判断第5行第2个点向右上的延伸时,有问题的应该是直接判断到这个点不能扩展到5,于是dp值就设为了1.
然而实际上,这个点可以做到4,并且为点(6,1)提供路径达到最大值5.
各位如果有WA#4的问题可以参考一下,希望能帮助到你.
by ZlycerQan @ 2017-10-18 20:19:37
@xtr劫 万分感谢
by XYloto @ 2017-11-01 15:20:19
@Mr_Spade 太感谢了，调了半天
by SeKong @ 2017-11-07 10:22:04
@Mr_Spade 感谢
by marshal王子祥 @ 2017-12-16 21:03:31
http://luogu
by hongzy @ 2017-12-17 21:48:17
@Mr_Spade 感谢!
by xxxhhh @ 2018-03-13 21:17:36
感谢
by EightSixSun @ 2018-04-15 17:46:11
@Mr_Spade 感谢