90pts 第二个点wa了求助 做法为堆+dp

peapapig @ 2024-07-11 09:13:22

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+9;
long long r,c,a[N][N],f[N][N],ans;
long long w[5]={0,0,1,-1};
long long s[5]={1,-1,0,0};
priority_queue <pair<long long,pair<long long ,long long>>> q;
int main(){
    scanf("%lld%lld",&r,&c);
    for(int i=1;i<=r;i++)for(int j=1;j<=r;j++){
        scanf("%lld",&a[i][j]); 
        q.push({a[i][j],{i,j}});
    }
    while(!q.empty()){
        auto k=q.top();q.pop();
        f[k.second.first][k.second.second]++;
        for(int i=0;i<4;i++)if(k.first>a[k.second.first+w[i]][k.second.second+s[i]])f[k.second.first+w[i]][k.second.second+s[i]]=max(f[k.second.first+w[i]][k.second.second+s[i]],f[k.second.first][k.second.second]);
        ans=max(f[k.second.first][k.second.second],ans);
    }
    printf("%lld",ans);
    return 0;
}

by peapapig @ 2024-07-11 10:33:58

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+9;
long long r,c,a[N][N],f[N][N],ans;
long long w[5]={0,0,1,-1};
long long s[5]={1,-1,0,0};
priority_queue <pair<long long,pair<long long ,long long>>> q;
int main(){
    scanf("%lld%lld",&r,&c);
    for(int i=1;i<=r;i++)
        for(int j=1;j<=r;j++){
            scanf("%lld",&a[i][j]);
            f[i][j]=1;
            q.push({-a[i][j],{i,j}});
        }
    while(!q.empty()){
        auto k=q.top();q.pop();
        for(int i=0;i<4;i++)if(a[k.second.first][k.second.second]>a[k.second.first+w[i]][k.second.second+s[i]])f[k.second.first][k.second.second]=max(f[k.second.first+w[i]][k.second.second+s[i]]+1,f[k.second.first][k.second.second]);
        ans=max(f[k.second.first][k.second.second],ans);
    }
    printf("%lld",ans);
    return 0;
}

现在是这个代码