首页 > 代码库 > 洛谷p1732 活蹦乱跳的香穗子 二维DP
洛谷p1732 活蹦乱跳的香穗子 二维DP
今天不BB了,直接帖原题吧 地址>>https://www.luogu.org/problem/show?pid=1732<<
题目描述
香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值
跳的规则是这样的,香穗子可以向上下左右四个方向跳到相邻的格子,并且她只能往价值更高(这里是严格的大于)的格子跳.
香穗子可以从任意的格子出发,在任意的格子结束,
那么她最多能跳几次?
输入输出格式
输入格式：
第一行n,m,表示田野的长和宽
接下来n行,每行m个数,表示该格的价值
输出格式：
一个数,表示最多跳得次数
输入输出样例
输入样例#1：
2 2 2 5 -1 3输出样例#1：
2说明
n,m<=100
这是二维DP样板,是DP中的豪杰,相较普通DP,思路和顺序也有些变化.
这题里,搜索函数是核心内容,建立数学模型也是比较重要(洛谷题解中有多种模型,构建不同也导致他们后续主函数运算部分难易不一,但其实不关键,能写出来就够了)
下面是我构建的搜索函数(疯狂膜洛谷题解大佬):
int sgs(int i,int j) { int k=0; if(a[i][j]!=-1) return a[i][j]; if(i-1>=1&&map[i-1][j]<map[i][j]) { a[i][j]=max(a[i][j],sgs(i-1,j)+1); k=1; } if(j+1<=m&&map[i][j+1]<map[i][j]) { a[i][j]=max(a[i][j],sgs(i,j+1)+1); k=1; } if(i+1<=n&&map[i+1][j]<map[i][j]) { a[i][j]=max(a[i][j],sgs(i+1,j)+1); k=1; } if(j-1>=1&&map[i][j-1]<map[i][j]) { a[i][j]=max(a[i][j],sgs(i,j-1)+1); k=1; } if(k==0) a[i][j]=0; return a[i][j]; }
其中map是储存地图数字的数组,a是储存"跳到这个格子的最大次数",对每一个点map[i,j]讨论跳到这个点所需的最大步数,再在主函数中forfor遍历全图就可以找到答案.
函数的查找方法是对该点的上下左右询问,看是否有比该点数字小的点,如果有比他小的(即可从那个点跳到该点),就拿a[i,j]和a[那个点]+1来取最大值.
其中值得注意的一行:
if(a[i][j]!=-1) return a[i][j];
-1是在主函数中输入数据是赋值的.意为"未被询问的",被询问后就会有值(比大于0),依次区分,如果没有这行,那程序的运行会慢好多哦~~~
以下是ac代码:
#include<iostream>
using namespace std;
int max(int a,int b)
{
return a>b?a:b;
}
int map[101][101],a[101][101];
int n,m;
int sgs(int i,int j)
{
int k=0;
if(a[i][j]!=-1) return a[i][j];
if(i-1>=1&&map[i-1][j]<map[i][j])
{
a[i][j]=max(a[i][j],sgs(i-1,j)+1);
k=1;
}
if(j+1<=m&&map[i][j+1]<map[i][j])
{
a[i][j]=max(a[i][j],sgs(i,j+1)+1);
k=1;
}
if(i+1<=n&&map[i+1][j]<map[i][j])
{
a[i][j]=max(a[i][j],sgs(i+1,j)+1);
k=1;
}
if(j-1>=1&&map[i][j-1]<map[i][j])
{
a[i][j]=max(a[i][j],sgs(i,j-1)+1);
k=1;
}
if(k==0) a[i][j]=0;
return a[i][j];
}
int main()
{
int i,j,way=0;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
cin>>map[i][j];
a[i][j]=-1;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
way=max(way,sgs(i,j));
cout<<way<<endl;
}
注意边界的判断哦~(比心)
洛谷p1732 活蹦乱跳的香穗子 二维DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。