90,#4为啥过不了

P1434 [SHOI2002] 滑雪

c_yanye_w @ 2024-12-31 22:42:13

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
struct node
{
    int h,x,y;
    friend bool operator < (node a,node b)
    {
        return a.h>b.h; 
    }
}d[10005];
bool check(node a,node b)
{
    return abs(a.x-b.x)+abs(a.y-b.y)==1 && a.h>b.h;
}
int r,c,tot,dp[10005],ans;
int main()
{
    scanf("%d %d",&r,&c);
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            int h;
            scanf("%d",&h);
            d[++tot]=node{h,i,j};
        }
    }
    sort(d+1,d+tot+1);
    dp[1]=1;
    for(int i=2;i<=tot;i++)
    {
        int x=d[i].x,y=d[i].y;
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(check(d[j],d[i]))
                dp[i]=max(dp[j]+1,dp[i]);
        }
        ans=max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}

by b__b @ 2024-12-31 23:14:31

ans可能为0,但是无论如何必定会存在一个长度为1的路径


|