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

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

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
const int N = 30;
struct plane{
	int t,d,l;
}p[N];

bool st[N];       //初值为0 
int n;

bool dfs(int u,int time)    //u是U架飞机成功降落,time表示前一架落地的时间 
{
	if(u >= n)
		return true;
	//考虑u+1谁落地 
	for(int i=0; i< n; i++)
	{
		if(!st[i])     //表示第i架飞机没落,当st[i]为false时,条件成立,代码块中的语句将被执行。
		{
			st[i] = true;          //true就是赋值为1 ,在这里标记为降落 
			if(p[i].t + p[i].d < time)
			{
				st[i] = false; //回溯,回溯到dfs之前 
				return false;
			}
			
			int t = max(time, p[i].t) + p[i].l;
			if(dfs(u + 1,t))
			{
				return true;
			}
				
			st[i] = false;
		} 
		 
	}
	return false;
}

void solve()
{
	cin >> n;
	for(int i = 0; i<n; i++)
	{
		cin>> p[i].t >> p[i].d >> p[i].l;
	}
	
	if(dfs(0,0))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
		
	for(int i = 0; i<n; i++)
		st[i] = false;
}


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