45分求助
查看原帖
45分求助
490651
zcy942楼主2022/10/29 18:18

一个不知道是什么算法(就算是dfs吧 的程序

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

inline long long read(){
	long long ret=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') if(c=='-') f=-1;
	while(c>='0' && c<='9') ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
	return ret*f;
}

struct point{
	long long x,y;
}a[510];

long long n,k,ans=0;

bool cmp(point xx,point yy){
	if(xx.x==yy.x) return xx.y<yy.y;
	return xx.x<yy.x;
}

void dfs(long long i,long long tot,long long kk){
	ans=max(ans,tot);
	for(long long j=i+1;j<n;j++){
		if((a[j].x>=a[i].x) && (a[j].y>=a[i].y)){
			long long s=a[j].x-a[i].x+a[j].y-a[i].y-1;
			if((kk-s)>=0) dfs(j,tot+1,kk-s);
		}
	}
}

int main(){
//	freopen("point.in","r",stdin);
//	freopen("point.out","w",stdout);

	n=read(),k=read();
	ans=k;
	for(long long i=0;i<n;i++){
		a[i].x=read(),a[i].y=read();
	}
	sort(a,a+n,cmp);
	
	for(long long i=0;i<n;i++) dfs(i,k+1,k);
	printf("%lld",ans);

//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
2022/10/29 18:18
加载中...