第一次写dfs,感觉没问题啊,样例都没过
查看原帖
第一次写dfs,感觉没问题啊,样例都没过
1165228
o_CIHL楼主2024/3/8 23:17
#include<stdio.h>
int n,m[21]={0};
int t[21],d[21],l[21];

int max(int a,int b){
	if(a>b) return a;
	else return b;
}

int dfs(int u,int time){
	if(u>=n)
		return 1;
	for(int i=0;i<n;i++){
		if(!m[i]){
			if(t[i]+d[i]<time){
				continue;
			}
			m[i]=1;
			time=max(time,t[i])+l[i];
			if(dfs(u+1,time)){
				m[i]=0;
				return 1;
			}
			m[i]=0;
		}
	} 
	return 0;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d%d%d",&t[i],&d[i],&l[i]);
		}
		for(int i=0;i<n;i++){
			m[i]=0;
		}
		if(dfs(0,0)) printf("YES\n");
		else printf("NO\n");
	} return 0;
}
2024/3/8 23:17
加载中...