tzd__emmm @ 2022-10-31 22:49:50
using namespace std;
vector <int> g[1001];
int a[1010][1010];
int num[1010][1010],dp[1001][1001];
int n,m;
int l;
int ans=1;
int op[1100];
int pos;
void dfs(int now,int deep)
{
if(!g[now].size())
{
ans=max(ans,deep);
return;
}
for(int i=0;i<g[now].size();i++)
{
int t=g[now][i];
dfs(t,deep+1);
}
}
int main()
{
cin>>n>>m;
int maxn=0;
memset(a,0x7f,sizeof a);
int p=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
num[i][j]=++p;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
/*if(a[i][j]>maxn)
{
maxn=a[i][j];
l=num[i][j];
}*/
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]>a[i+1][j])
{
g[num[i][j]].push_back(num[i+1][j]);
}
if(a[i][j]>a[i][j+1])
{
g[num[i][j]].push_back(num[i][j+1]);
}
if(a[i][j]>a[i-1][j])
{
g[num[i][j]].push_back(num[i-1][j]);
}
if(a[i][j]>a[i][j-1])
{
g[num[i][j]].push_back(num[i][j-1]);
}
}
}
/*for(int i=1;i<=num[n][n];i++)
{
cout<<i<<": ";
for(int j=0;j<g[i].size();j++)
{
cout<<g[i][j]<<" ";
}
cout<<endl;
}*/
for(int i=1;i<=p;i++)
{
dfs(i,1);
}
//dfs(l,1);
cout<<ans;
return 0;
}
by waauto @ 2022-11-01 09:55:10
by waauto @ 2022-11-01 09:55:35
*剪枝
by waauto @ 2022-11-01 10:18:16
可以参考一下我刚刚写的记忆化搜索。
#include <bits/stdc++.h>
#define name(x) #x
#define debug(x) cout<<name(x)<<"="<<x<<endl;
using namespace std;
int a[105][105],f[105][105];
int dfs(int x,int y){
if(f[x][y])return f[x][y];
f[x][y]=1;
if(a[x+1][y]<a[x][y])f[x][y]=max(f[x][y],1+dfs(x+1,y));
if(a[x-1][y]<a[x][y])f[x][y]=max(f[x][y],1+dfs(x-1,y));
if(a[x][y+1]<a[x][y])f[x][y]=max(f[x][y],1+dfs(x,y+1));
if(a[x][y-1]<a[x][y])f[x][y]=max(f[x][y],1+dfs(x,y-1));
return f[x][y];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,m,ans=1;
cin>>n>>m;
memset(a,0x3f,sizeof(a));
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<=n;j++)
ans=max(ans,dfs(i,j));
cout<<ans;
return 0;
}
by lyc1001 @ 2022-11-01 21:59:57
@RainL wsg去比赛了吗?是不是还在封校?生活过得顺利吗?
by tzd__emmm @ 2022-11-01 22:28:59
@RainL 太6了
by ShanireZ @ 2022-11-02 21:53:18
你们这都是怎么认识的