首页 > 代码库 > 洛谷 P1732 活蹦乱跳的香穗子
洛谷 P1732 活蹦乱跳的香穗子
题目描述
香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值
跳的规则是这样的,香穗子可以向上下左右四个方向跳到相邻的格子,并且她只能往价值更高(这里是严格的大于)的格子跳.
香穗子可以从任意的格子出发,在任意的格子结束,
那么她最多能跳几次?
输入输出格式
输入格式：
第一行n,m,表示田野的长和宽
接下来n行,每行m个数,表示该格的价值
输出格式：
一个数,表示最多跳得次数
输入输出样例
输入样例#1：
2 22 5-1 3
输出样例#1：
2
说明
n,m<=100
答案保证小于Maxlongint
屠龙宝刀点击就送
记忆化搜索
#include <cstdio>long long f[1510][1510],value[1510][1510];long long n,m,maxn=-1;long long fx[5]={1,-1,0,0},fy[5]={0,0,-1,1};long long max(long long a,long long b){ return a>b?a:b;}long long qr(long long &x){ x=0;bool f=1; char ch=getchar(); while(ch>‘9‘||ch<‘0‘) { if(ch==‘-‘) f=0; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+(long long)ch-48; ch=getchar(); } x=f?x:(~x)+1;}long long dfs(long long u,long long v){ if(f[u][v]) return f[u][v]; long long p=0; for(long long i=0;i<4;++i) { long long x=u+fx[i],y=v+fy[i]; if(x>=1&&x<=n&&y>=1&&y<=m&&value[x][y]>value[u][v]) p=max(dfs(x,y),p); } f[u][v]=p+1; return f[u][v];}int main(){ qr(n); qr(m); for(long long i=1;i<=n;i++) for(long long j=1;j<=m;++j) qr(value[i][j]); for(long long i=1;i<=n;i++) for(long long j=1;j<=m;++j) maxn=max(maxn,dfs(i,j)); printf("%lld",maxn-1); return 0;}
洛谷 P1732 活蹦乱跳的香穗子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。