40，求调

zifeiwoye @ 2025-01-11 18:01:23

#include <bits/stdc++.h>

using namespace std;

map<int,pair<int,int> > mapp;

int ma[105][105],r,c,t[10005],dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};

int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cin>>ma[i][j];
            t[r*i+j-r]=ma[i][j];
            mapp[ma[i][j]]=make_pair(i,j);
        }
    }
    sort(t+1,t+r*c+1);
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            ma[mapp[t[r*i+j-r]].first][mapp[t[r*i+j-r]].second]=i*r-r+j;
            mapp[r*i+j-r]=make_pair(mapp[t[r*i+j-r]].first,mapp[t[r*i+j-r]].second);
        }
    }
    int dp[105]={1},maxx=1;
    dp[1]=1;
    for(int i=2;i<=r*c;i++)
    {
        int x=mapp[i].first,y=mapp[i].second;
        for(int j=0;j<4;j++)
        {
            if(ma[x+dx[j]][y+dy[j]]<ma[x][y])
                dp[i]=max(dp[ma[x+dx[j]][y+dy[j]]]+1,dp[i]);
        }
        maxx=max(maxx,dp[i]);
    }
    cout<<maxx;
    return 0;
}

by be_the_person @ 2025-01-11 18:40:26

@zifeiwoye AC代码

#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=110;
int n,m,ans;
int map[maxn][maxn];
int dp[maxn][maxn];//dp[i][j]表示(i,j)点的最长路
struct node
{
    int x,y,val;
}a[10010];
int tot;
struct cmp
{ 
    bool operator()(node x,node y)
    {
        return x.val<y.val;
    }
};
priority_queue <node,vector<node>,cmp> q;
void judge(int x,int y)
{
    if(map[x-1][y]>map[x][y])
        dp[x][y]=max(dp[x][y],dp[x-1][y]+1);
    if(map[x+1][y]>map[x][y])
        dp[x][y]=max(dp[x][y],dp[x+1][y]+1);
    if(map[x][y-1]>map[x][y])
        dp[x][y]=max(dp[x][y],dp[x][y-1]+1);
    if(map[x][y+1]>map[x][y])
        dp[x][y]=max(dp[x][y],dp[x][y+1]+1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            dp[i][j]=1;
            a[++tot].val=map[i][j];
            a[tot].x=i;
            a[tot].y=j;
            q.push(a[tot]);
        }
    while(!q.empty())
    {
        node now=q.top();
        int xx=now.x;
        int yy=now.y;
        judge(xx,yy);
        q.pop();
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,dp[i][j]);
    printf("%d",ans);
    return 0;
}