一、Description
和poj1088同样的题目
【题目描述】
benben喜欢滑雪。（以下简叙）在一个(R*C(R,Cleq100))的整数矩阵上找一条高度严格递减的最长路。起点任意，但每次只能沿着上下左右4个方向之一走一格，并且不能走出矩阵外。如图所示，最长路是按照高度25,24,23,...,2,1 这样走，长度为25。矩阵中的数均为0~100.
【输入格式】
有多组数据。
第一行为一个整数N，表示数据组数。 对于每组数据，第一行包括一个字符串和两个整数R,C，为此滑雪者的姓名和矩阵的长宽。
【输出格式】
对于每组数据，输出一行，格式为： name: answer
name为当前数据的滑雪者姓名，answer为你的答案。
【输入输出样例】
输入：
2
Feldberg 10 5
56 14 51 58 88
26 94 24 39 41
24 16 8 51 51
76 72 77 43 10
38 50 59 84 81
5 23 37 71 77
96 10 93 53 82
94 15 96 69 9
74 0 62 38 96
37 54 55 82 38
Spiral 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
输出：
Feldberg: 7
Spiral: 25
二、Soulution
这是一道动态规划的题目，(dp[i][j])表示到达((i,j))点的时候最长路的值，初始化都为1
-
首先按照整数矩阵的值的大小对每个点从大到小排序，然后更新每个点的(dp[][])值，也就是状态转移;
-
当((i,j))点的整数值小于周围的点并且，(dp[i][j])小于周围某个点的(dp+1)的时候，表示周围的某个点可以下滑到((i,j))，那么更新(dp[i][j])为周围那个点的(dp+1)。
这里为什么要先从大到小排序呢？可以将整个整数矩阵理解成一座座山相连，局部最大的值就是一个山的山峰。我们想得到其中一个山的高度（由该山峰出发的最大下滑距离），由于一开始dp值都是1，必须先得到较高的点的dp值，才能根据它更新较低点的dp值。
《算法基础与在线实践》书上动态规划这一节有讲这个poj1088的题目，递推也有两种思路。
-
一种是“人人为我”，就是由上下左右的点更新当前的点的dp值（也就是我下面代码采用的）
-
另一种就是“我为人人”，就是由当前的点，更新上下左右的点的dp值
当然两者更新的时候都要先判度四周的点是否符合条件：一是没有越界；二是要从高的点滑向低的点；
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct Node{
int value;
int i;
int j;
};
bool cmp(const Node a, const Node b) //结构体的比较函数
{
return a.value > b.value;
}
int main()
{
int t;
cin >> t;
string name;
int row, col;
while(t--) {
cin >> name >> row >> col;
vector<vector<int>> map(row, vector<int>(col, 0));
vector<vector<int>> dp(row, vector<int>(col, 1)); // dp[i][j]表示到(i,j)点的时候最大的下滑距离
// 初始都是1！！！
struct Node nodes[row*col];
int k = 0;
for(int i = 0; i < row; ++i) {
for(int j = 0; j < col; ++j) {
cin >> map[i][j];
nodes[k].i = i;
nodes[k].j = j;
nodes[k].value = map[i][j];
k++;
}
}
sort(nodes, nodes + row*col, cmp); // 按照value从大到小排序
dp[nodes[0].i][nodes[0].j] = 1;
int ans = 0;
for(int i = 1; i < row*col; ++i) {
int x = nodes[i].i;
int y = nodes[i].j;
int value = nodes[i].value;
// 由上、下、左、右的点更新该点的值
if (y-1 >= 0 && value < map[x][y-1]) {
dp[x][y] = max(dp[x][y], dp[x][y-1] + 1);
}
if (y+1 < col && value < map[x][y+1]) {
dp[x][y] = max(dp[x][y], dp[x][y+1] + 1);
}
if (x-1 >= 0 && value < map[x-1][y]) {
dp[x][y] = max(dp[x][y], dp[x-1][y] + 1);
}
if (x+1 < row && value < map[x+1][y]) {
dp[x][y] = max(dp[x][y], dp[x+1][y] + 1);
}
ans = max(ans, dp[x][y]);
}
cout << name << ":" << " " << ans << endl;
}
return 0;
}