路人甲2003 @ 2019-05-19 16:54:34
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
bool b[105][105];
int dp[105][105];
int m,n,sumn,minn=100000000,sx,sy;
int x[4]={0,0,-1,1},y[4]={-1,1,0,0};
int dfs(int xx,int yy)
{
if(dp[xx][yy]) return dp[xx][yy];
int path=-1;
for(register int i=0;i<=3;++i)
{
if(!b[xx+x[i]][yy+y[i]]&&xx+x[i]>0&&xx+x[i]<=n
&&yy+y[i]>0&&yy+y[i]<=m&&a[xx][yy]>a[xx+x[i]][yy+y[i]])
{
path=max(path,dfs(xx+x[i],yy+y[i])+1);
}
}
return dp[xx][yy]=path;
}
int main()
{
cin>>n>>m;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
{
scanf("%d",&a[i][j]);
if(a[i][j]<minn){sx=i;sy=j;minn=a[i][j];}
}
dp[sx][sy]=1;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
{
dfs(i,j);
}
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j) sumn=max(sumn,dp[i][j]);
/*
for(register int i=1;i<=n;++i)
{
for(register int j=1;j<=m;++j)
{
printf("%d ",dp[i][j]);
}
cout<<endl;
}
cout<<endl;*/
printf("%d",sumn);
return 0;
}
wa1,10
by hater @ 2019-05-19 17:28:27
dp了解一下
by 路人甲2003 @ 2019-05-24 15:33:40
@hater 这个是记搜,也是dp啊