POJ1088 动态规划

题意：

解答：

　这个题目和最长子序列什么的极为类似。只是之前都是一维，如今变成二维的了。仅此而已。因此我们能够想办法把它先变成一维的。

• 先用一个结构体存储这个矩阵，这就成一维的了。

struct Node{

   int height;  //这个是高度

   int r;       //x坐标

   int c;       //y坐标

}a[100*100+5];

然后我们能够依据height排序。从最高点開始考虑，，有点贪心的意思。。

和单源最短路径dijkstra类似。

• 然后还是要存一个矩阵的~

int ma[100+2][100+2][2];

//ma[][][0] :存储的是高度

  ma[][][1] :这里将它作为DP递归，存储的是:到这个点时最长的长度

• 然后我们依照那个结构体进行遍历。，每次遍历到一个节点i，我们考虑他的周围四个点，假设高度小于他们，更新（而且要取最大当中最大的DP值+1）。否则为1。（是不是和最长上升子序列一样？？？）
• 结果就是当中的最大值

代码：

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstdio>

#include <cstring>

using namespace std;

struct Node{

   int height;

   int r;

   int c;

}a[100*100+5];

int dx[] = {0,0,1,-1};

int dy[] = {1,-1,0,0};

int ma[100+2][100+2][2];

int R,C;

bool cmp(const Node &a, const Node &b){

     return a.height>b.height;

}

int main()

{

    //freopen("data.txt",'r');

    scanf("%d%d",&R,&C);

    memset(a,0,sizeof(a));

    memset(ma,0,sizeof(ma));

    int k = 0;

    for(int i = 1; i<=R; i++){

        for(int j = 1; j<=C; j++){

            scanf("%d",&a[k].height);

            ma[i][j][0] = a[k].height;

            a[k].r = i;

            a[k++].c = j;

        }

    }

    sort(a,a+k,cmp);

    int ans = 1;

    for(int i = 0; i<R*C; i++){

        int maxx = 0;

        for(int j =0; j<4; j++){

            int x = a[i].r + dx[j];

            int y = a[i].c + dy[j];

            if(x<1 || x>R || y<1 || y>C) continue;

            if(ma[x][y][0] > a[i].height)

                maxx = max(maxx, ma[x][y][1]);

        }

        ma[a[i].r][a[i].c][1] = maxx+1;

        ans = max(ans,maxx+1);

    }

    printf("%d\n",ans);

    return 0;

}