首次发帖,所以有什么不妥之处还请各位多多指教哈~~
http://acm.pku.edu.cn/JudgeOnline/problem?id=1088
滑雪
Description
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。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
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
Sample Output
25
Source
SHTSC 2002
2.题目分析:
这是一道比较典型的DP的题,至少,十有八九的人看到这道题就知道这是用动态规划(其实就是一道变相的最长下降子序列),要想写出状态转移方程也不难,唯一的难点可能在于这个是二维的。所以排序和生成状态时就应该换种方法。
首先,贪心肯定不行,例如
1
|
24
|
9
|
8
|
3
|
24
|
24
|
10
|
7
|
4
|
20
|
19
|
12
|
6
|
5
|
17
|
18
|
13
|
2
|
2
|
16
|
15
|
14
|
2
|
25
|
可以从中看出,从最高的贪和从最低的开始贪都是不行的,由数学归纳法可以证明从次高点或次低点开始贪心也不行,依次类推。从图的角度理解,该题目中,每个非边界点可以四向走、边界非顶点点可以三向、顶点可以二向,所以此问题可以等效于从A到B的最短路径的问题,这是不能贪心的。
那么为什么可以动规呢?首先,我们假设每个点与其他点都不连通,那么每个点的最长路径为1。当我们从(相对)最低点(初始状态S0)开始循环时,每一个与它相邻的点与它之间的决策P1都可以初始状态S0来定,在此决策之后,得到相邻点新的状态。可以证明的是,当相对低点的状态都确定之后,所有高点可以滑的长度(状态Sr,r<=sum_of_points)都可以由邻接的低点的状态决定(通过决策)。在其中找最长即可。所以可以用动规。
确定动规之后,先说最重要的:状态转移方程。
Dp[r,c,x]表示:
循环走到第x个高度的时候,各个点的最长滑坡路径状态。
其中所有dp[r,c,0]=0;
Dp[adja_r,adja_c,x]=dp[adja_r,adja_c,x-1], h[adja_r,adja_c,x]<=h[r,c,x-1]
Dp[adja_r,adja_c,x]=max( dp[adja_r,adja_c,x-1], dp[r,c,x-1]+1), h[adja_r,adja_c]>h[r,c]
注意每个点有四个adjacent points。
由此,我们可以写出dp()过程的伪代码:
From 高度小的点 to 高度大的点
对于该点的四向相邻点(注意不要越界)
If (该点h<邻点h)
If (该点dp[][]+1 > 邻点dp[][])
{邻点 dp[][] = 该点 dp[][]+1;
Longest = max(邻点dp[][], longest);
}
最后输出longest即可。
3.原程序:
1
#include <iostream>
2
#include <fstream>
3
4
using namespace std;
5
6
int n,r,c;
7
int h[102][102],len[102][102];
8
int longestslope=1;
9
struct Point
{
10
int row;
11
int column;
12
int val;
13
}p[10002];
14
int dir[4][2]=
{0,-1,-1,0,0,1,1,0};
15
16
void dp()
{
17
for (int i=1; i<=r*c; i++)
{
18
int curr=p[i].row;
19
int curc=p[i].column;
20
21
for (int j=0; j<=3; j++)
{
22
int adjar = curr+dir[j][0];
23
int adjac = curc+dir[j][1];
24
//judge if the adjacent point is out of bound;
25
if ( adjar<1 || adjar>r || adjac<1 || adjac>c ) continue;
26
27
if (h[curr][curc] < h[adjar][adjac])
28
if ( len[curr][curc]+1 > len[adjar][adjac] )
{
29
len[adjar][adjac] = len[curr][curc]+1;
30
if (len[adjar][adjac] > longestslope)
31
longestslope = len[adjar][adjac];
32
}
33
}
34
}
35
36
}
37
38
void qsort(int l, int r)
{
39
…
40
}
41
42
int main()
{
43
int n;
44
int cnt=0;
45
scanf("%d %d",&r,&c);
46
for (int i=1; i<=r; i++)
47
for (int j=1; j<=c; j++)
{
48
scanf("%d",&h[i][j]);
49
p[++cnt].val=h[i][j];
50
p[cnt].row=i;
51
p[cnt].column=j;
52
len[i][j]=1;
53
}
54
55
qsort(1,r*c);
56
dp();
57
printf("%d\n",longestslope);
58
return 0;
59
}
60