刚学dp的萌新求助

_TMT_ @ 2019-12-22 19:13:50

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,sum,f[10005],ans;
struct node
{
    int id,h;
}a[10005];
bool cmp(node A,node B)
{
    return A.h>B.h;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        int x;
        scanf("%d",&x);
        sum++;
        a[sum].id=sum;
        a[sum].h=x;
    }
    sort(a+1,a+sum+1,cmp);
    for(int i=1;i<=sum;i++)f[i]=1;
    for(int i=1;i<=sum;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j].id==a[i].id-1||a[j].id==a[i].id+1||a[j].id==a[i].id-m||a[j].id==a[i].id+m)f[i]=max(f[i],f[j]+1);
        }
    }
    for(int i=1;i<=sum;i++)ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}

by _TMT_ @ 2019-12-22 19:17:34

加了句

for(int i=1;i<=sum;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j].h!=a[i].h)
            if(a[j].id==a[i].id-1||a[j].id==a[i].id+1||a[j].id==a[i].id-m||a[j].id==a[i].id+m)f[i]=max(f[i],f[j]+1);
        }
    }

现在90分，第一个点过不掉，头疼

by Jiao_Xie @ 2019-12-22 19:29:33

DAG最长路问题 给个记忆化搜索就行

by Jiao_Xie @ 2019-12-22 19:30:53

#include <iostream>
using namespace std;
int n,m,d[101][101],maxn,a[101][101],dlt[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int dp(int i,int j)
{
    if(d[i][j]) return d[i][j];
    d[i][j]=1;
    for(int k=0;k<4;k++)
    {
        int di=i+dlt[k][0],dj=j+dlt[k][1];
        if(di>0 && di<=n && dj>0 && dj<=m && a[i][j]>a[di][dj])d[i][j]=max(d[i][j],dp(di,dj)+1);
    }
    return d[i][j];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            maxn=max(maxn,dp(i,j));
    cout<<maxn;
    return 0;
}

by Jiao_Xie @ 2019-12-22 19:32:07

用d[i][j]表示从(i,j)开始滑的最大长度

往上下左右拓展就行

by _TMT_ @ 2019-12-22 21:18:33

@Jiao_Xie 谢谢