L9211080N0225 @ 2019-07-07 21:27:28
#include<bits/stdc++.h>
using namespace std;
int a[101][101];
int f[101][101];
int n,m;
int ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
cin>>a[i][j];
f[i][j]=1;
}
}
for(int k=1;k<=n;++k)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(a[i][j]>a[i-1][j])
{
f[i][j]=max(f[i][j],f[i-1][j]+1);
}
}
for(int j=2;j<=m;++j)
{
if(a[i][j]>a[i][j-1])
{
f[i][j]=max(f[i][j],f[i][j-1]+1);
}
}
for(int j=m-1;j>=1;--j)
{
if(a[i][j]>a[i][j+1])
{
f[i][j]=max(f[i][j],f[i][j+1]+1);
}
}
}
for(int i=n;i>=1;--i)
{
for(int j=1;j<=m;++j)
{
if(a[i][j]>a[i+1][j])
{
f[i][j]=max(f[i][j],f[i+1][j]+1);
}
}
for(int j=2;j<=m;++j)
{
if(a[i][j]>a[i][j-1])
{
f[i][j]=max(f[i][j],f[i][j-1]+1);
}
}
for(int j=m-1;j>=1;--j)
{
if(a[i][j]>a[i][j+1])
{
f[i][j]=max(f[i][j],f[i][j+1]+1);
}
}
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
ans=max(ans,f[i][j]);
}
}
printf("%d",ans);
return 0;
}反馈是answer too long
by 已注销ZdCpmQy3 @ 2019-07-07 23:03:42
话说不是记忆化深搜吗
#include<bits/stdc++.h>
using namespace std;
int n,a1[101][101],b1[101][101],b,a,xx,yy,ans=0,fx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int dfs(int x,int y){
if (b1[x][y]) return b1[x][y];
int tmp=0;
for(int i=0;i<=3;i++){
xx=x+fx[i][0];
yy=y+fx[i][1];
if (xx>=1 && yy>=1 && xx<=a && yy<=b && a1[x][y]<a1[xx][yy]) tmp = max(dfs(xx,yy),tmp);
}
return b1[x][y]=tmp+1;
}
int main(){
cin>>a>>b;
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++) cin>>a1[i][j];
}
memset(b1,0,sizeof(b1));
for (int i=1;i<=a;i++) for 通过fx数组判断方向，将该格最长个数直接赋值。