题目描述
Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可行的滑坡为24－17－16－1（从24开始，在1结束）。当然25－24－23－...－3－2－1更长。事实上，这是最长的一条。
输入输出格式
输入格式：
输入的第一行为表示区域的二维数组的行数R和列数C（1≤R，C≤100）。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。
输出格式：
输出区域中最长滑坡的长度。
输入输出样例
输入样例#1：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例#1： 25
[思路]：
简单dp，虽然它在有技巧的搜索里面（其实dp好像和记忆化搜索差不多逃），然而怎么做呢？
dp[i][j]只能从四个方向走过来,而且四个方向的点的高度要大于这个点,于是就可以了.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int maxn=;
const int minn=-;
inline int read()
{
char c = getchar();
int x = , f = ;
while(c < '' || c > '')
{
if(c == '-') f = -;
c = getchar();
}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int f[][];
int a[][];
int n,m,sum;
int dp(int x,int y)
{
if (f[x][y]) return f[x][y];
int sum=;
if (x->)
if (a[x-][y]>a[x][y])
sum=max(sum,dp(x-,y));
if (x+>)
if (a[x+][y]>a[x][y])
sum=max(sum,dp(x+,y));
if (y->)
if (a[x][y-]>a[x][y])
sum=max(sum,dp(x,y-));
if (y+>)
if (a[x][y+]>a[x][y])
sum=max(sum,dp(x,y+));
f[x][y]=sum+;
return f[x][y];
}
int main()
{
n=read();
m=read();
for (int i=; i<=n; i++)
for (int j=; j<=m; j++)
{
a[i][j]=read();
}
for (int i=; i<=n; i++)
for (int j=; j<=m; j++)
{
if (f[i][j]==)
{
f[i][j]=dp(i,j);
}
sum=max(sum,f[i][j]);
}
printf("%d",sum);
return ;
}
然后我看了看题解，发现有记忆化搜索就厚颜无耻地粘过来了（嘿嘿）
by 一扶苏一 更新时间: 2018-02-24 15:57
/*本题f数组表示当前坐标点滑下去的最大长度。
状态转移方程：f[i][j]=max{f[i±1][j]+1,f[i][j±1}+1,f[i][j]}
dfs函数采用逆推法。
*/
#include<cstdio>
#define maxn 110
#define max(a,b) a>b?a:b
using namespace std;
int map[maxn][maxn],f[maxn][maxn],r,c,dfs(int,int),m;
/*
map存跑道，f存答案，
r，c为纵坐标横坐标，
dfs搜索函数，两个变量分别为被搜索点的纵、横坐标。
底下函数x，y打反了， 即x代表纵坐标，x代表横坐标，别看晕了
m为最长跑道长度，全局变量初始值为0。
*/
int main(){
scanf("%d%d",&r,&c);
for(int i=;i<=r;i++)
for(int j=;j<=c;j++){
scanf("%d",&map[i][j]);f[i][j]=;
/*
输入，因为自己滑到自己的长度是1，所以答案数组初始化为1。
*/
}
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
m=max(m,dfs(i,j)); //进行搜索，如果结果比已知答案更大就更新。
printf("%d",m); //输出答案
return ;
}
inline int dfs(int x,int y){ //搜索函数，其中x代表纵坐标，y代表横坐标，一开始打反了，后面懒得改了，别看晕了
if(f[x][y]!=) return f[x][y];
int b=;
/*
以下四句if，每个括号中前四句条件是否到达边界，最后一条件判断是否当前坐标比搜索坐标高。
*/
if(x>=&&y>=&&x<r&&y<=c&&map[x][y]>map[x+][y]) b=max(b,(dfs(x+,y)+));
if(x>=&&y>=&&x<=r&&y<c&&map[x][y]>map[x][y+]) b=max(b,(dfs(x,y+)+));
if(x>&&y>=&&x<=r&&y<=c&&map[x][y]>map[x-][y]) b=max(b,(dfs(x-,y)+));
if(x>=&&y>&&x<=r&&y<=c&&map[x][y]>map[x][y-]) b=max(b,(dfs(x,y-)+));
f[x][y]=max(f[x][y],b); //防止4个if都不成立即b为0的情况。故取最大值
return f[x][y];
}