滑雪---poj1088（动态规划+记忆化搜索）

题目链接：http://poj.org/problem?id=1088

有两种方法

一是按数值大小进行排序，然后按从小到大进行dp即可；

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;

#define N 110
#define met(a, b) memset(a, b, sizeof(a))

typedef long long LL;

int n, m, dp[N][N], A[N][N];
int dir[4][2] = { {-1, 0},{1, 0},{0, -1},{0, 1} };

struct node
{
    int x, y, w;
    friend bool operator<(node p, node q)
    {
        return p.w < q.w;
    }
}a[N*N];

int main()
{
    while(scanf("%d %d", &m, &n)!=EOF)
    {
        met(a, 0);
        met(A, 0);
        int len = 0;
        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
            {
                scanf("%d", &A[i][j]);
                a[len].x = i;
                a[len].y = j;
                a[len++].w = A[i][j];
            }
        }
        sort(a, a+len);
        met(dp, 0);
        int ans = 0;
        for(int i=0; i<len; i++)
        {
            int Max = 0;
            for(int j=0; j<4; j++)
            {
                int p = a[i].x + dir[j][0];
                int q = a[i].y + dir[j][1];
                if(A[p][q] < a[i].w )
                    Max = max(Max, dp[p][q]);
            }
            dp[a[i].x][a[i].y] = Max + 1;
            ans = max(ans, Max+1);
        }
        printf("%d
", ans);
    }
    return 0;
}
/*
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
*/

还一种是不排序，用记忆化搜索：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>

using namespace std;

#define N 110
#define met(a, b) memset(a, b, sizeof(a))

typedef long long LL;

int n, m, dp[N][N], A[N][N], ans;
int dir[4][2] = { {-1, 0},{1, 0},{0, -1},{0, 1} };

int dfs(int x, int y)
{
    if(dp[x][y]) return dp[x][y];
    int Max = 0;
    for(int i=0; i<4; i++)
    {
        int px = x+dir[i][0];
        int py = y+dir[i][1];
        if(px>0 && py>0 && px<=m && py<=n && A[px][py]<A[x][y])
            Max = max(Max, dfs(px, py));
    }
    dp[x][y] = Max+1;
    ans = max(ans, dp[x][y]);
    return dp[x][y];
}

int main()
{
    while(scanf("%d %d", &m, &n)!=EOF)
    {
        met(A, 0);
        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
                scanf("%d", &A[i][j]);
        }
        met(dp, 0);

        ans = 0;

        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
            {
                dfs(i, j);
            }
        }
        printf("%d
", ans);
    }
    return 0;
}
/*
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
*/