蒟蒻刷DP题80分求助

P1434 [SHOI2002] 滑雪

HyGeoIceFairy @ 2020-11-01 13:28:17

总体思路：

将节点从高到低排序依次扩展，可以保证是最优解

WARNING：极差码风注意

#include <iostream>
#include <cstdio>
#include <algorithm>
using std::sort;

struct Node
{
    int x, y, h;
}s[10900];

struct OriginalGraph
{
    int h, w;
}g[109][109];

int r, c, ans;

int v(int pos1, int pos2)
{
    return ((pos1-1)*r+pos2);
}

int comp(const Node s1, const Node s2)
{
    return s1.h>s2.h;
}

int main()
{
    scanf("%d%d", &r, &c);
    for(register int i=1; i<=r; ++i)
    {
        for(register int j=1; j<=c; ++j)
        {
            scanf("%d",&g[i][j].h);
            s[v(i,j)].h=g[i][j].h;
            s[v(i,j)].x=i;
            s[v(i,j)].y=j;
            g[i][j].w=1;
        }
    }
    sort(s+1, s+r*c+1, comp);
    for(register int i=1; i<=r*c; ++i)
    {
        if(g[s[i].x-1][s[i].y].h>g[s[i].x][s[i].y].h&&g[s[i].x-1][s[i].y].w+1>g[s[i].x][s[i].y].w&&s[i].x-1>0)
        {
            g[s[i].x][s[i].y].w=g[s[i].x-1][s[i].y].w+1;
        }
        if(g[s[i].x][s[i].y-1].h>g[s[i].x][s[i].y].h&&g[s[i].x][s[i].y-1].w+1>g[s[i].x][s[i].y].w&&s[i].y-1>0)
        {
            g[s[i].x][s[i].y].w=g[s[i].x][s[i].y-1].w+1;
        }
        if(g[s[i].x+1][s[i].y].h>g[s[i].x][s[i].y].h&&g[s[i].x+1][s[i].y].w+1>g[s[i].x][s[i].y].w&&s[i].x+1<=r)
        {
            g[s[i].x][s[i].y].w=g[s[i].x+1][s[i].y].w+1;
        }
        if(g[s[i].x][s[i].y+1].h>g[s[i].x][s[i].y].h&&g[s[i].x][s[i].y+1].w+1>g[s[i].x][s[i].y].w&&s[i].y+1<=c)
        {
            g[s[i].x][s[i].y].w=g[s[i].x][s[i].y+1].w+1;
        }
        if(g[s[i].x][s[i].y].w>ans)
        {
            ans=g[s[i].x][s[i].y].w;
        }
    }
    printf("%d",ans);
    return 0;
}

1和2点就是过不去……

被黄题难住果然还是不应该……

请指教我！（他力本愿）

by 小仓朝阳 @ 2020-11-01 13:45:38

这不是记忆化搜索吗qaq

by HyGeoIceFairy @ 2020-11-01 13:46:37

@小仓朝阳差不多的（大嘘），请帮助我！

by 小仓朝阳 @ 2020-11-01 14:01:01

你去看一下就知道了qaq

by Echidna @ 2020-11-01 14:02:11

~~码风奇特~~

您大可以使用这种方式来减短您的代码长度，提升代码可读性。

int xa[4]={1,-1,0,0};
int ya[4]={0,0,1,-1};

for(int j=0;j<4;j++)
    if(a[x+xa[j]][y+ya[j]]>a[x][y])
        f[x][y]=max(f[x][y],f[x+xa[j]][y+ya[j]]+1);

这样写不仅减短而且还能提高可读性。

by Echidna @ 2020-11-01 14:22:13

错误原因找到了，您的v(x,y)有问题。

by Echidna @ 2020-11-01 14:27:09

这是我修改过了的您的代码 ~~（稍微优化了一下码风）~~

关于v(x,y)函数的问题，我使用了一个额外的变量k解决这个问题。你每读入一个数，就把k加一，这样最后s数组中有用的范围就是[1,k-1]，既简便又好用。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node
{
    int x, y, h;
}s[10900];
struct OriginalGraph
{
    int h, w;
}g[109][109];
int r, c, ans,k=1;
int comp(const Node s1, const Node s2)
{
    return s1.h>s2.h;
}
int xa[4]={1,-1,0,0};
int ya[4]={0,0,1,-1};
int main()
{
    scanf("%d%d", &r, &c);
    for(int i=1; i<=r; ++i)
    {
        for(int j=1; j<=c; ++j)
        {
            scanf("%d",&g[i][j].h);
            s[k].h=g[i][j].h;
            s[k].x=i;
            s[k++].y=j;
            g[i][j].w=1;
        }
    }
    sort(s+1, s+k, comp);
    for(int i=1; i<=r*c; ++i)
    {
        int x=s[i].x;
        int y=s[i].y;
        for(int j=0;j<4;j++)
            if(g[x+xa[j]][y+ya[j]].h>g[x][y].h)
                g[x][y].w=max(g[x][y].w,g[x+xa[j]][y+ya[j]].w+1);
    }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            ans=max(ans,g[i][j].w);
    printf("%d\n",ans);
    return 0;
}

其实我觉得写代码的时候不要让一些其他的东西阻碍思路才是最重要的。

最后我再帖一下我用您的方法的AC代码吧。 ```cpp #include<iostream> #include<algorithm> using namespace std; const int N=110; int f[N][N]; int a[N][N]; int n,m; struct Node{ int x,y,h; }nds[N*N]; bool cmp(Node n1,Node n2){ return n1.h>n2.h; } int k=1; int xa[4]={1,-1,0,0}; int ya[4]={0,0,1,-1}; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>a[i][j]; nds[k].x=i,nds[k].y=j,nds[k++].h=a[i][j]; } sort(nds+1,nds+k,cmp); for(int i=1;i<=k;i++){ int x=nds[i].x; int y=nds[i].y; for(int j=0;j<4;j++) if(a[x+xa[j]][y+ya[j]]>a[x][y])//这个方向可以拓展 f[x][y]=max(f[x][y],f[x+xa[j]][y+ya[j]]+1); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<f[i][j]<< "\t"; cout<<endl; } int ans=-1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=max(ans,f[i][j]); cout<<(ans+1)<<endl; } ```

by Echidna @ 2020-11-01 14:37:04

@Cirno_Baka

by HyGeoIceFairy @ 2020-11-01 16:40:40

@某学oi的蒟蒻非常感谢您！！！

by HyGeoIceFairy @ 2020-11-01 16:54:38

温暖的世界

by Echidna @ 2020-11-02 08:03:13

@Cirno_Baka 不用谢