首次發帖,所以有什么不妥之處還請各位多多指教哈~~
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