全RE,用的floyd
查看原帖
全RE,用的floyd
691024
Qingshui_King楼主2023/10/19 17:21

将数组开大也没用

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,k,x[N],y[N];
long long f[N][N];
int ma(int i,int j){
	return abs(x[i]-x[j])+abs(y[i]-y[j]);
}
int floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j&&x[i]<=x[j]&&y[i]<=y[j])f[i][j]=ma(i,j)-1;
			else f[i][j]=INT_MAX;
		}
	}
	floyd();
	long long ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(f[i][j]<=k)ans=max(ans,ma(i,j)-f[i][j]+k+1);
		}
	}
	cout<<ans;
}
2023/10/19 17:21
加载中...