滑雪（DP）

题目描述

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（从24开始，在1结束）。当然25－24－23―┅―3―2―1更长。事实上，这是最长的一条。

输入输出格式

输入格式：

输入的第一行为表示区域的二维数组的行数R和列数C（1≤R，C≤100）。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。

输出格式：

输出区域中最长滑坡的长度。

输入输出样例

输入样例#1： 复制

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

输出样例#1： 复制

25

这是一道二维的DP，这题比较多的是偏向使用记忆化搜索，我用的是循环

首先，我们可以发现此题有 3 个输入的要点。

1. 一个点的高度
2. 这个点的横坐标
3. 这个点的纵坐标

既然是二维的DP，那么就要使用二维的图标分析
先看下面的一张图：

这是比较小的图，可以更好的分析。
i 表示行数，j 表示列数，在这里，可以很容易的就看出来最长的路线是一条螺旋的曲线向下滑。那么，我们是怎么想到这么一条曲线的呢？部分人就会很自然的想到，首先将高度排序，然后从小到大选一条最大的路线。这是不行的，如果怎么做的话，就没有考虑到坐标的影响，这也就是题目的一个限制的条件，只能向相邻的点滑动，而且只能由高处往低处滑动。此题也不能贪心，因为贪心，很容易会发现反例，如下图：

如果总是从最高点出发的话，那么这条路不一定是最大的。这图算比较小的，设想一下，按照这样的模型把图放大，会是什么样的结果。

那么，我们应该怎么去分析这道题呢？能不能把这道题转化一下，转化成其他的DP题。如果说把这二维的坐标全部转化为一维的数组……（在内存中，没有二维的数组，所有的东西都是线性一维的，二维的东西只是基于人们的假想，如果说你可以试试在开机的时候把内存拔出来看看上面的二维数组长什么样子……）

接下来换一张大一点的图：

这个二维的图，如果说把它转化为一维的图的话，可以发现数组是这么排列的：
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
因为这数组原来全都是一维的，但是由于要将它改造成 5 * 5 的矩阵，所以在上图中它执行了每五列换一次行。
根据最终的结果来看，它其实是这样的一个序列：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
也就是一个有坐标限制的最长上升子序列
那么，我们可以开一个结构数组来存储一个点的信息，它的信息包括它的 x ，y 坐标和它的高度，结构数组是一维的，但是它又可以同时存储多个信息，所以它是最佳的选择，而且它还可以用 sort 进行排序。
所以，最终的结论就是，首先把整个地图接进来，然后把每个点的信息存入一个结构数组里面，再对它们的高度进行排序，排序完之后再仿照求最长上升子序列的方法来求最大的滑行长度。

补充：二维数组一维化的方法，用当前的行数乘以最大列数再加上当前列数。
若是以 i 为当前行数，r 为最大行数，j 为当前列数，c 为最大列数，则表示为 :
( i * c + j ) 至于原因，对着上面的二维数组自己模拟一下就明白了。

以下是代码：（参考《算法基础与在线实践》）

#include <iostream>
#include <algorithm>

using namespace std;

int f[105][105];
int a[105][105];

struct Node
{
    int x;
    int y;
    int h;
}node[10005];

struct rule
{
    bool operator() (const Node & s1,const Node & s2)
    {
        return s1.h < s2.h;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    int r,c,ans = 0;
    cin >> r >> c;
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> a[i][j];
            node[i * c + j].h = a[i][j];
            node[i * c + j].x = i;
            node[i * c + j].y = j;
            f[i][j] = 1;
        }
    }
    sort(node,node + r * c,rule());
    for (int i = 0; i < r * c; ++i)
    {
        int r1 = node[i].x;
        int c1 = node[i].y;
        if (r1 > 0 && a[r1][c1] > a[r1 - 1][c1])
        {
            f[r1][c1] = max(f[r1][c1],f[r1 - 1][c1] + 1);
        }
        if (c1 > 0 && a[r1][c1] > a[r1][c1 - 1])
        {
            f[r1][c1] = max(f[r1][c1],f[r1][c1 - 1] + 1);
        }
        if (r1 < r - 1 && a[r1][c1] > a[r1 + 1][c1])
        {
            f[r1][c1] = max(f[r1][c1],f[r1 + 1][c1] + 1);
        }
        if (c1 < c - 1 && a[r1][c1] > a[r1][c1 + 1])
        {
            f[r1][c1] = max(f[r1][c1],f[r1][c1 + 1] + 1);
        }
    }
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            ans = max(ans,f[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}