SHOI2002滑雪 题解

题目链接

一张地图,起点任意,只能上下左右走。

题目要求求出地图上最长的一条单调减序列。

考虑学搜索时候刷过的水题,求出类似地图上两点最短路,我们采用DP思想,更新一个dis数组。

有dp方程:$dis_{to}=min\{dis_{from}+1\}$

类似这个题目,我们也可以采用类似的方法,维护一个dp[x][y]数组,用来表示走到点(x,y)的最长的单调递减序列路径。

当从一个坐标$from$移动到另一个坐标$to$时候,有dp方程:

我们可以进行记忆化搜索。

但是题目没有给定具体起点,那么在搜索的时候,每一个点都要当做起点遍历一次!

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using LL=long long;
using Pair=std::pair<int,int>;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;

const int maxn=110;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};//上下左右位移

int dp[maxn][maxn];
int G[maxn][maxn];//存边

int n,m;

inline bool judge(Pair pot)//判断坐标是否在区域内
{
return pot.first>=1 && pot.second>=1
&& pot.first<=n && pot.second<=m;
}

int dfs(Pair pos)
{
int fx=pos.first,fy=pos.second;

if(dp[fx][fy])//已经访问过
return dp[fx][fy];

int ans=1;
for(int i=0;i<4;i++)
{
int tx=fx+dx[i],ty=fy+dy[i];
Pair to=std::make_pair(tx,ty);

if(judge(to) && G[tx][ty]<G[fx][fy])//坐标在区域内且序列单调减
ans=std::max(dfs(to)+1,ans);//不要漏了+1
}
return dp[fx][fy]=ans;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",G[i]+j);

int ans=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=std::max(dfs(std::make_pair(i,j)),ans);//遍历每一个起点

printf("%d\n",ans);
return 0;
}