返回题解分享
讨论 / 题解分享/ 帖子详情

飞机降落(编程题) - 题解

搜索

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 11;
int N, T[MAX_N], D[MAX_N], L[MAX_N];
bool have_answer,used[MAX_N];
void dfs(int x,int tim)
{
	if(have_answer)
	{
		return ;
	}
	if(x==N)//降落完了 
	{
		have_answer = 1;
		return;
	}
	for(int i = 1;i<=N;++i)
	{
		if(!used[i] && tim <= T[i] + D[i])//如果没有降落过 
		{
			used[i] = 1;
			dfs(x+1, max(T[i],tim) + L[i]);
			if(have_answer)
			{
				return ;
			}
			used[i] = 0;
		} 
	}
}
void solve()
{
	have_answer = 0;
	cin>>N;
	for(int i = 1;i <= N;++i)
	{
		cin>>T[i]>>D[i]>>L[i];
		used[i] = 0;//是否降落过,得提前清空一下 
	}
	dfs(0,0);
	if(have_answer)
	{
		cout<<"YES"<<endl;
	} 
	else
	{
		cout<<"NO"<<endl;
	}
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
	
	return 0;            
}
0 回复 0 转发 1 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!