这是一个简单的问题。你并不需要打印路径。

状态方程dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i+1][j],dp[i][j+1]);

14003395

10285

option=com_onlinejudge&Itemid=8&page=show_problem&problem=1226" style="margin:0px; padding:0px; color:rgb(153,0,0); text-decoration:none">Longest Run on a Snowboard

Accepted

C++

0.026

2014-08-07 11:43:51

枚举每一个点进行遍历，使用记忆化搜索。要不会超时。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<list>

#include<string>

#include<sstream>

#include<ctime>

using namespace std;

#define _PI acos(-1.0)

#define INF (1 << 10)

#define esp 1e-6

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> pill;

/*===========================================

===========================================*/

#define MAXD 100 + 10

char name[MAXD];

int m,n,ans;

int dp[MAXD][MAXD];

int mat[MAXD][MAXD];

int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

int DP(int x,int y){

    if(dp[x][y] != -1)

        return dp[x][y];

    dp[x][y] = 1;

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

        int _x = dir[i][0] + x;

        int _y = dir[i][1] + y;

        if(_x >= 0 && _y >=0 && _x < n && _y < m && mat[x][y] < mat[_x][_y]){

            dp[x][y] = max(dp[x][y],DP(_x,_y) + 1);

        }

    }

    ans = max(ans,dp[x][y]);

    return dp[x][y];

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%s%d%d",name,&n,&m);

        int pos_x,pos_y;

        int MIN = INF;

        memset(dp,-1,sizeof(dp));

        for(int i = 0 ; i < n ; i++)

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

                scanf("%d",&mat[i][j]);

                if(mat[i][j] < MIN){

                    MIN = mat[i][j];

                    pos_x = i;

                    pos_y = j;

                }

            }

        ans = 0;

        for(int i = 0 ; i < n ; i++)

            for(int j = 0 ; j < m ; j++)

                DP(i,j);

        printf("%s: %d\n",name,ans);

    }

    return 0;

}