井——— @ 2018-09-14 10:20:30
#include<iostream>
using namespace std;
int m,n,ans=-1;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int a[110][110];
void dfs(int x,int y,int len)
{
if(x<1||x>m||y<1||y>n) //防止越界
return;
for(int i=0;i<4;i++)
{
if(a[x+dx[i]][y+dy[i]]<a[x][y]) //找周围小的点进行操作
{
dfs(x+dx[i],y+dy[i],len+1);
ans=max(ans,len); //更新最大值
}
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
//易知:如果周围有比这个点高的点,
// 那么这个点就不是最优解
if(a[i][j]>a[i+1][j]&&i+1<=m)
if(a[i][j]>a[i][j+1]&&j+1<=n)
if(a[i][j]>a[i][j-1]&&j-1>0)
dfs(i,j,1); //长度为1,开始寻找
}
cout<<ans;
return 0;
}
最后只得了20分,求大佬告诉我思维的局限性在哪,1个tle,7个wa
by stepsys @ 2018-09-14 12:03:54
TLE是因为这题要记忆化搜索
by 梧桐灯 @ 2018-09-14 12:32:38
更新最大值有点问题。。
by 7KByte @ 2018-09-14 12:57:04
用dp来做
by 7KByte @ 2018-09-14 12:58:30
先按数值从小到大排(用稀疏矩阵),再做dp,不过这题最好用记忆化搜索来做
by 7KByte @ 2018-09-14 12:58:44
@井———
by 井——— @ 2018-09-14 14:26:56
@犇羴鱻赑骉 麻烦大佬点一下哪里,我看了好久了
by 井——— @ 2018-09-14 14:27:47
@online_wlq 谢谢大佬,我知道正解,但我想搞明白我哪里写错了
by 梧桐灯 @ 2018-09-16 21:11:10
@井———
最好每次dfs return前写 因为你的if语句可能每一次都不对,但如果此时恰是最大值时,就无法更新了(语文不好的我已经尽力了QAQ)