30tps（和楼下不一样）求助

Dcchen @ 2024-07-24 21:01:10

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int nx[]={0,0,0,1,-1},ny[]={0,1,-1,0,0};
struct ST{
    int x,y;
}; 
map<int,ST> mp;
int r,c,a[105][105],dp[105][105],ans;
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>a[i][j];
            mp[a[i][j]].x=i;
            mp[a[i][j]].y=j;
        }
    }
    for(int i=1;i<=1000002;i++){
        if(mp[i].x!=0){
            for(int j=1;j<=4;j++){
                int dx=mp[i].x+nx[j];
                int dy=mp[i].y+ny[j];
                if(a[dx][dy]<a[mp[i].x][mp[i].y]) dp[mp[i].x][mp[i].y]=max(dp[dx][dy],dp[mp[i].x][mp[i].y]);
            }
             dp[mp[i].x][mp[i].y]++;
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
}

by Obijeb @ 2024-07-24 21:20:23

能问一下大概思路吗，你这个写法有点清奇 @Dcchen

by Dcchen @ 2024-07-24 21:23:40

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int nx[]={0,0,0,1,-1},ny[]={0,1,-1,0,0};
struct ST{
    int x,y;
}; //坐标 
map<int,ST> mp;//mp存储每个数字的坐标 
int r,c,a[105][105],dp[105][105],ans;//dp是每一个点能走的长度 
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>a[i][j];
            mp[a[i][j]].x=i;
            mp[a[i][j]].y=j;
        }
    }
    for(int i=1;i<=1000002;i++){
        if(mp[i].x!=0){//找到一个数，如果这个数的x坐标不为0，则这个数存在 
            for(int j=1;j<=4;j++){//四个方向延伸 
                int dx=mp[i].x+nx[j];
                int dy=mp[i].y+ny[j];
                if(a[dx][dy]<a[mp[i].x][mp[i].y]) dp[mp[i].x][mp[i].y]=max(dp[dx][dy],dp[mp[i].x][mp[i].y]);//如果这个方向能走，找步数最大的 
            }
             dp[mp[i].x][mp[i].y]++;//加上自己这个点 
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ans=max(ans,dp[i][j]);
        }
    }//找到最大的点的步数 
    cout<<ans;
}

@Obijeb

by Dcchen @ 2024-07-24 21:26:30

dp公式的意思就是说取自己本身目前的能走步数与能到的点走的步数最大值 @Obijeb

by Obijeb @ 2024-07-24 21:27:58

@Dcchen 有一个可能的问题

本题有一些点的高度相同

导致map只能存下最后那个

by Dcchen @ 2024-07-24 21:29:46

哦。。。原来是这样

谢谢（+关注）

by Obijeb @ 2024-07-24 21:34:01

@Dcchen 没过可以继续@我

by Obijeb @ 2024-07-24 21:38:18

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int nx[]={0,0,0,1,-1},ny[]={0,1,-1,0,0};
struct ST{
    int x,y;
    int h;
}plc[105*105];
int num=0;
int r,c,a[105][105],dp[105][105],ans;//dp是每一个点能走的长度 
bool cmp(ST a,ST b)
{
    return a.h<b.h;
}
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>a[i][j];
            plc[++num].h=a[i][j];
            plc[num].x=i;
            plc[num].y=j;
        }
    }
    sort(plc+1,plc+num+1,cmp);//按高度从小到大排序
    for(int i=1;i<=num;i++){
        {
            for(int j=1;j<=4;j++){//四个方向延伸 
                int dx=plc[i].x+nx[j];
                int dy=plc[i].y+ny[j];
                if(a[dx][dy]<plc[i].h) dp[plc[i].x][plc[i].y]=max(dp[dx][dy],dp[plc[i].x][plc[i].y]);//如果这个方向能走，找步数最大的 
            }
             dp[plc[i].x][plc[i].y]++;//加上自己这个点 
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            ans=max(ans,dp[i][j]);
        }
    }//找到最大的点的步数 
    cout<<ans;
}

在你的模板上改了一个用结构体sort的递推写法

by Dcchen @ 2024-07-24 22:25:49

谢

经过“你”不懈的努力，“我”终于过了