首次發帖,所以有什么不妥之處還請各位多多指教哈~~

  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個整數,代表高度h0<=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

可以從中看出,從最高的貪和從最低的開始貪都是不行的,由數學歸納法可以證明從次高點或次低點開始貪心也不行,依次類推。從圖的角度理解,該題目中,每個非邊界點可以四向走、邊界非頂點點可以三向、頂點可以二向,所以此問題可以等效于從AB的最短路徑的問題,這是不能貪心的。

       那么為什么可以動規呢?首先,我們假設每個點與其他點都不連通,那么每個點的最長路徑為1。當我們從(相對)最低點(初始狀態S0)開始循環時,每一個與它相鄰的點與它之間的決策P1都可以初始狀態S0來定,在此決策之后,得到相鄰點新的狀態。可以證明的是,當相對低點的狀態都確定之后,所有高點可以滑的長度(狀態Srr<=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
 4using namespace std;
 5
 6int n,r,c;
 7int h[102][102],len[102][102];
 8int longestslope=1;
 9struct Point {
10    int row;
11    int column;
12    int val;
13}
p[10002];
14int dir[4][2]={0,-1,-1,0,0,1,1,0};
15
16void 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>|| 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
38void qsort(int l, int r) {
39        …
40}

41
42int 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