POJ 1088 滑雪 解题报告
解题思路：dp加记忆化搜索，不算难，注意细节就行
#include<iostream>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<fstream>
#include<iomanip>
#pragma warning(disable:4996)
#define INF 0x3f3f3f3f
#define ll long long
#define PI acos(-1.0)
const int N = 1000010;
const int maxn = 1e9;
using namespace std;
int a[105][105];
int dp[105][105];
int dx[5] = { 0,0,0,1,-1 };
int dy[5] = { 0,1,-1,0,0 };
int r, c,ans;
int dfs(int i, int j)
{
if (dp[i][j] > 0)
return dp[i][j];
int tem = 1;//要初始化返回值为1，因为可能这个点就是最高点，下面for循环中判断可能不执行
for (int k = 1; k < 5; k++)
{
int t = 0;
if (i + dx[k] >= 1 && i + dx[k] <= r && j + dy[k] >= 1 && j + dy[k] <= c)
{
if (a[i + dx[k]][j + dy[k]] > a[i][j])
{
t = dfs(i + dx[k], j + dy[k]) + 1;
tem = max(tem, t);
}
}
}
dp[i][j] = tem;
return tem;
}
int main()
{
ans = -1;
cin >> r >> c;
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
dp[i][j] = dfs(i, j);
ans = max(dp[i][j], ans);
}
}
cout << ans << endl;
}