dp专题 滑雪

求一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。

最长的滑坡

dp[i][j]表示从i，j出发的最长的滑坡
递推的顺序：由高度从低到高，因为要知道dp[i][j]，必须知道周围所有比自己矮的dp值。
记忆化递归：可以不按从低到高的顺序直接递归。

人人为我：dp[i][j]由周围比自己矮的推导出来。
d[i][j]=max(dp[i-1][j]), dp[i+1][j], dp[i][j-1], dp[i][j+1]):a[x][y]>d[i][j]

我为人人：由dp[i][j]去推导比自己高的
dp[i-1][j]=max(dp[i-1][j],d[i][j]); dp[i+1][j]=max(dp[i+1][j],d[i][j]);
dp[i][j-1]=max(dp[i][j-1],d[i][j]); dp[i][j-1]=max(dp[i][j-1],d[i][j]);
					

人人为我:
#include<bits/stdc++.h>
using namespace std;

struct node
{
    int h;
    int i;
    int j;
}H[10005];

int a[105][105];
int dp[105][105];

int cmp(node &a, node &b)
{
    return a.h<b.h;
}

int main()
{
    int r, c, p=1;
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&a[i][j]);
            H[p].h=a[i][j];
            H[p].i=i, H[p].j=j;
            p++,dp[i][j]=1;
        }
    }
    sort(H+1, H+p, cmp);
    int ans=1;
    for(int k=1;k<p;k++)
    {
        int i=H[k].i, j=H[k].j;
        if(i+1<=r&&a[i+1][j]<a[i][j])
            dp[i][j]=max(dp[i][j], dp[i+1][j]+1);
        if(i-1>=1&&a[i-1][j]<a[i][j])
            dp[i][j]=max(dp[i][j], dp[i-1][j]+1);
        if(j+1<=c&&a[i][j+1]<a[i][j])
            dp[i][j]=max(dp[i][j], dp[i][j+1]+1);
        if(j-1>=1&&a[i][j-1]<a[i][j])
            dp[i][j]=max(dp[i][j], dp[i][j-1]+1);

        ans=max(ans, dp[i][j]);
    }
    printf("%d\n",ans);

    return 0;
}

我为人人：
#include<bits/stdc++.h>
using namespace std;

struct node
{
    int h;
    int i;
    int j;
}H[10005];

int a[105][105];
int dp[105][105];

int cmp(node &a, node &b)
{
    return a.h<b.h;
}

int main()
{
    int r, c, p=1;
    scanf("%d%d",&r,&c);
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&a[i][j]);
            H[p].h=a[i][j];
            H[p].i=i, H[p].j=j;
            p++,dp[i][j]=1;
        }
    }
    sort(H+1, H+p, cmp);
    int ans=1;
    for(int k=1;k<p;k++)
    {
        int i=H[k].i, j=H[k].j;
        if(i+1<=r&&a[i+1][j]>a[i][j])
            dp[i+1][j]=max(dp[i][j]+1, dp[i+1][j]);
        if(i-1>=1&&a[i-1][j]>a[i][j])
            dp[i-1][j]=max(dp[i][j]+1, dp[i-1][j]);
        if(j+1<=c&&a[i][j+1]>a[i][j])
            dp[i][j+1]=max(dp[i][j]+1, dp[i][j+1]);
        if(j-1>=1&&a[i][j-1]>a[i][j])
            dp[i][j-1]=max(dp[i][j]+1, dp[i][j-1]);

        ans=max(ans, dp[i][j]);
    }
    printf("%d\n",ans);

    return 0;
}

记忆化递归：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int a[110][110];
int s[110][110];
int xx[]={0, 1, 0, -1};
int yy[]={1, 0, -1, 0};
int n, m;

int dp(int i, int j)
{
    if(s[i][j]!=-1)
        return s[i][j];

    s[i][j]=1;
    for(int k=0; k<4; k++)
    {
        int x=i+xx[k];
        int y=j+yy[k];

        if(x>=0&&x<n&&y>=0&&y<m)
        {
            if(a[x][y]>a[i][j])
            s[i][j]=max(s[i][j], dp(x, y)+1);
        }
    }
    return s[i][j];


}

int main()
{
    int max_s=1;
    cin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
            s[i][j]=-1;

        }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            s[i][j]=dp(i, j);
            max_s=max(max_s, s[i][j]);
        }

    cout<<max_s;

    return 0;
}