求调 wa#1#2
查看原帖
求调 wa#1#2
948995
Yurinaxu楼主2024/7/9 08:59
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ans[10005],fx[10005],dp[10005],sum,a[105][105],f[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
vector<int> v[10005],u[10005];
priority_queue<long long,vector<long long>,greater<long long> > q;
void dfs(){
	for(int i=1;i<=n*m;i++){
		if(fx[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int t=q.top(),len=v[q.top()].size();
		q.pop();
		ans[++ans[0]]=t;
		for(int i=0;i<len;i++){
			fx[v[t][i]]--;
			if(fx[v[t][i]]==0){
				q.push(v[t][i]);
			}
		}
	}
}
void bfs(int k){
	int len=u[k].size();
	dp[k]=max(dp[k],1);
	for(int i=0;i<len;i++){
		dp[u[k][i]]=max(dp[u[k][i]],dp[k]+1);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int o=0;o<4;o++){
				x=i+f[o][0],y=j+f[o][1];
				if(x<1 || x>n || y<1 || y>m){
					continue;
				}
				if(a[i][j]>a[x][y]){
					v[(i-1)*n+j].push_back((x-1)*n+y);
					u[(x-1)*n+y].push_back((i-1)*n+j);
					fx[(x-1)*n+y]++;
				}
			}
		} 
	}
	dfs();
	for(int i=n*m;i>=1;i--){
		bfs(ans[i]);
	}
	for(int i=1;i<=n*m;i++){
		sum=max(sum,dp[i]);
	}
	cout<<sum;
    return 0;
}
2024/7/9 08:59
加载中...