首次發(fā)帖，所以有什么不妥之處還請(qǐng)各位多多指教哈~~

2.題目分析：

       這是一道比較典型的DP的題，至少，十有八九的人看到這道題就知道這是用動(dòng)態(tài)規(guī)劃（其實(shí)就是一道變相的最長(zhǎng)下降子序列），要想寫(xiě)出狀態(tài)轉(zhuǎn)移方程也不難，唯一的難點(diǎn)可能在于這個(gè)是二維的。所以排序和生成狀態(tài)時(shí)就應(yīng)該換種方法。

       首先，貪心肯定不行，例如

可以從中看出，從最高的貪和從最低的開(kāi)始貪都是不行的，由數(shù)學(xué)歸納法可以證明從次高點(diǎn)或次低點(diǎn)開(kāi)始貪心也不行，依次類推。從圖的角度理解，該題目中，每個(gè)非邊界點(diǎn)可以四向走、邊界非頂點(diǎn)點(diǎn)可以三向、頂點(diǎn)可以二向，所以此問(wèn)題可以等效于從A到B的最短路徑的問(wèn)題，這是不能貪心的。

       那么為什么可以動(dòng)規(guī)呢？首先，我們假設(shè)每個(gè)點(diǎn)與其他點(diǎn)都不連通，那么每個(gè)點(diǎn)的最長(zhǎng)路徑為1。當(dāng)我們從（相對(duì)）最低點(diǎn)（初始狀態(tài)S₀）開(kāi)始循環(huán)時(shí)，每一個(gè)與它相鄰的點(diǎn)與它之間的決策P₁都可以初始狀態(tài)S₀來(lái)定，在此決策之后，得到相鄰點(diǎn)新的狀態(tài)。可以證明的是，當(dāng)相對(duì)低點(diǎn)的狀態(tài)都確定之后，所有高點(diǎn)可以滑的長(zhǎng)度（狀態(tài)Sr，r<=sum_of_points）都可以由鄰接的低點(diǎn)的狀態(tài)決定（通過(guò)決策）。在其中找最長(zhǎng)即可。所以可以用動(dòng)規(guī)。

       確定動(dòng)規(guī)之后，先說(shuō)最重要的：狀態(tài)轉(zhuǎn)移方程。

 Dp[r,c,x]表示：

循環(huán)走到第x個(gè)高度的時(shí)候，各個(gè)點(diǎn)的最長(zhǎng)滑坡路徑狀態(tài)。

其中所有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]

注意每個(gè)點(diǎn)有四個(gè)adjacent points。

由此，我們可以寫(xiě)出dp()過(guò)程的偽代碼：

From 高度小的點(diǎn) to 高度大的點(diǎn)

       對(duì)于該點(diǎn)的四向相鄰點(diǎn)（注意不要越界）

              If （該點(diǎn)h<鄰點(diǎn)h）

                     If （該點(diǎn)dp[][]+1 > 鄰點(diǎn)dp[][]）

                            {鄰點(diǎn) dp[][] = 該點(diǎn) dp[][]+1;

                             Longest = max(鄰點(diǎn)dp[][], longest);

                            }

最后輸出longest即可。

 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>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
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