求助帖

题目传送门

测评记录传送门

第2个数据点WA了，90pts，求助。

dp[i][j]就是到(i,j)点的最长距离

先由高到低排序，从高到低bfs遍历渲染dp数组（从高到低使得任意一个已经被遍历过了的点都至少比从它自己开始大，因为它已经有至少1的基础的路径长度，并且已经bfs过了）

#include<iostream>
//#include<string>
#include<algorithm>
//#include<vector>
//#include<queue>
//#include<bits/stdc++.h>
//#include<stdio.h>
#include<cstdio>
//#include<stack>
//#include<map>
//#include<>
#define MAX 105
#define m_p(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define ll long long
#define ull unsigned long long
#define dl long double
#define ui unsigned int
#define inf 0x7FFFFFFF
#define REP(a,b,c) for(int a=b;a<c;a++)
using namespace std;
//int n;
//int a[MAX];
inline int rd(){
    register int x(0),f(1);register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
int dat[MAX][MAX];
int dp[MAX][MAX];
pair<int,int> st[10005];//x,y
int qx[500005];
int qy[500005];
int head = 0;
int tail = 0;
int ans = 0;
inline bool cmp(pair<int,int> p1 , pair<int,int> p2)
{
    return (dat[p1.first][p1.second]>dat[p2.first][p2.second]);
}
const int mv[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int main()
{
    int stcnt = 0;
    int n = rd();
    int m = rd();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dat[i][j] = rd();
            st[stcnt++] = m_p(i,j);
        }
    }
    sort(st,st+stcnt,cmp);
    for(int i=0;i<stcnt;i++)
    {
        //cout<<st[i].first<<' '<<st[i].second<<" : "<<dat[st[i].first][st[i].second]<<endl;
        if(!dp[st[i].first][st[i].second])
        {
            head = tail;
            qx[tail] = st[i].first;
            qy[tail] = st[i].second;
            dp[qx[tail]][qy[tail]] = 1;
            tail++;
            while(head<tail)
            {
                /*for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=m;j++)
                    {
                        cout<<dp[i][j]<<'\t';
                    }cout<<endl;
                }cout<<endl;*/
                int mx = qx[head];
                int my = qy[head];
                head++;
                for(int i=0;i<4;i++)
                {
                    int px = mx+mv[i][0]; 
                    int py = my+mv[i][1];
                    if(px>=1&&px<=n&&py>=1&&py<=m&&dat[mx][my]>dat[px][py])
                    {
                        if(dp[mx][my]+1>dp[px][py])
                        {
                            dp[px][py] = dp[mx][my]+1;
                            qx[tail] = px;
                            qy[tail] = py;
                            tail++;
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ans = max(ans,dp[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}