POJ 1088 滑雪

【题目链接】

动态规划，先将各点存入结构体，按照点值从小到大排序，从最小的点开始（假设这个点为A），判断周围四个方向有没有比这个点小的点值，如果有的话，判断 这个点值（点A的值） 与 周围点值+1 的大小，取最大值赋给点A。

if (map[que[i].x][que[i].y]>map[tx][ty])
{
 if (dp[que[i].x][que[i].y]>(dp[tx][ty]+1))
 dp[que[i].x][que[i].y]=dp[tx][ty]+1;
}

注意顺序，一定要从小到大，因为大的点值可以走的路径只与比他小的点值有关，然后遍历dp数组，找到最大值，就是需要的最长路径了。

/* 5 5 01 02 03 04 05 16 17 18 19 06 15 24 25 20 07 14 23 22 21 08 13 12 11 10 09 */
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct node
{
    int x;
    int y;
    int data;
}Node;
int cmp(Node a,Node b)
{
    return a.data<b.data;
}
int main()
{
    int next[][2]={1,0,0,1,-1,0,0,-1};
    int tx,ty,i,j,k,n,m,head=0,max=-1,flag;
    cin>>n>>m;
    int map[105][105],dp[105][105];
    memset(dp,0,sizeof(dp));
    Node que[10005];
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            dp[i][j]=1;
            cin>>map[i][j];
            que[head].data=map[i][j];
            que[head].x=i;
            que[head++].y=j;
        }
    }
    sort(que,que+m*n,cmp);
    for (i=0;i<n*m;i++)
    {
        flag=0;
        for (k=0;k<4;k++)
        {
            tx=que[i].x+next[k][0];
            ty=que[i].y+next[k][1];
            if (tx<1||tx>n||ty<1||ty>m)
            continue;
            if (map[que[i].x][que[i].y]>map[tx][ty])
            {
                dp[que[i].x][que[i].y]=dp[que[i].x][que[i].y]>(dp[tx][ty]+1)?dp[que[i].x][que[i].y]:(dp[tx][ty]+1);
                flag=1;
            }
        }
        if (flag==0)
        dp[que[i].x][que[i].y]=1;
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        max=max>dp[i][j]?max:dp[i][j];
    }
    cout<<max;
}