滑雪（dp或记忆化搜索）

题意：给你一个二维数组，求最长的递减路线的长度，只能向四个方向延伸。

解法1、dp【i】【j】以i、j结尾的最长路线长度。边界：每个数初值为1，

转移:从四周向i、j转移，if(a[i][j]>a[x][y]) dp[i][j] = max(dp[i][j] , dp[x][y]+1);

注意：这里需要按从小到大排序对点进行转移。否则答案有误。

//#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <string>

#include <stdio.h>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <string.h>

#include<time.h>

#include <vector>

#define ME(x , y) memset(x , y , sizeof(x))

#define SF(n) scanf("%d" , &n)

#define rep(i , n) for(int i = 0 ; i < n ; i ++)

#define INF  0x3f3f3f3f

#define mod 20191117

#define PI acos(-1)

using namespace std;

typedef long long ll ;

int n , m ;

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

int ma ;

int vis[109][109];

int v[109][109];

int dp[109][109];

int b[109][109];

struct node

{

    int x , y  , v;

}a[10009];

bool cmp(struct node a , struct node b)

{

    return a.v < b.v ;

}

int main()

{

    /*#ifdef ONLINE_JUDGE

    #else

        freopen("D:/c++/in.txt", "r", stdin);

        freopen("D:/c++/out.txt", "w", stdout);

    #endif*/

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

    int l = 0 ;

    for(int i = 0 ; i < n ; i++)//结构体存点值

    {

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

        {

            int x ;

            scanf("%d" , &x);

            b[i][j] = x ;

            a[l].x = i , a[l].y = j ;

            a[l++].v = x ;

        }

    }

    for(int i = 0 ; i < n ; i++)//边界值

    {

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

        {

            dp[i][j] = 1 ;

        }

    }

    sort(a , a + l , cmp);//按值排序

    for(int i = 0 ; i < l ; i++)//按从小到大的点进行转移

    {

        int x = a[i].x ;

        int  y = a[i].y ;

        for(int j = 0 ; j < 4 ; j++)//从四周转移到该点

        {

            int xx = x + dir[j][0];

            int yy = y + dir[j][1];

            if(xx >= 0 && xx < n && yy >= 0 && yy < m && b[xx][yy] < a[i].v)

            {

                dp[x][y] = max(dp[x][y] , dp[xx][yy] + 1);

            }

        }

    }

    int ans = 0 ;

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

    {

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

        {

            ans = max(ans , dp[i][j]);

        }

    }

    cout << ans << endl ;

    return 0;

}

解法二：记忆化搜索；

//#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdio.h>

#include <queue>

#include <stack>;

#include <map>

#include <set>

#include <ctype.h>

#include <string.h>

#include <vector>

#define ME(x , y) memset(x , y , sizeof(x))

#define SF(n) scanf("%d" , &n)

#define rep(i , n) for(int i = 0 ; i < n ; i ++)

#define INF  0x3f3f3f3f

#define mod 10

#define PI acos(-1)

using namespace std;

typedef long long ll ;

int a[109][109];

int dis[109][109];

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

int n , m ;

int cnt = 0 ;

int vis[109][109];

int dfs(int x , int y)

{

    if(dis[x][y] != 0){

        return dis[x][y];

    }

    int len =  1 ;//这里是关键。

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

    {

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

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

        if(xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] > a[x][y] )

        {

            len = max(len , dfs(xx , yy ) + 1);

        }

    }

    dis[x][y] = len ;//起始点的len是最大的。len表示该点到最长路径的终点的长度

    return len ;//最终返回该点所以路径中的最长路径长度。

}

int main()

{

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

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

    {

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

        {

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

        }

    }

    int ma = 0 ;

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

    {

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

        {

            ma = max(ma , dfs(i , j));//返回以所有点为起始点的最长路径。

        }

    }

    cout << ma << endl ;

    return 0;

}

巴特西

滑雪（dp或记忆化搜索）

最新文章

热门文章