飞机降落（dfs+贪心思想）

原题链接：4957. 飞机降落 - AcWing题库

思路分析：

通过读题易知，题目可以翻译为：

已知有 n 条线段，每条线段都可以在一定的区域内滑动。

需要我们来判断是否可以找到一种线段的分布方案，使得每条线段都不相交！

首先解释一下，为什么不能直接贪心来做？

因为题目的数据范围： 1 < = n < = 10 1<=n<=10 1<=n<=10

很显然数据比较小，所以正解的算法时间 复杂度较高（不是贪心）-> dfs

那么要怎么dfs呢？

很暴力

利用全排列的思想，对所有的线段进行搜索（每次搜索时用到了贪心的思想：即线段在满足条件的情况下，尽可能的往左靠）。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#define N 100
using namespace std;

typedef struct node
{
	int t, d, l;
}node;

node p[N];
int n;
bool st[N];

//u表示已经搜到了几个线段；	last表示上一个搜索到的线段的右端点坐标
int dfs(int u, int last)
{
	if (u > n)
	{
		return 1;
	}
	for (int i = 1; i <= n; i++)
	{
		int t = p[i].t, d = p[i].d, l = p[i].l;
		if (!st[i] && t+d>=last)	//如果没有访问过，并且该线段的最靠右的左端点在last之后！
		{
			st[i] = 1;
			if (dfs(u + 1, max(last, t) + l))//意思是，如果递归发现可以搜索到，就返回true，注意这里的 max(last,t)+l 表示的是刚搜索到的线段尽可能靠左时，它的右端点的坐标！！！
				return 1;
			st[i] = 0;
		}
	}

	return 0;
}

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		p[i] = { a,b,c };
	}
    //注意每次都对st[]初始化
	memset(st, 0, sizeof st);
	if (dfs(1, 0))
		cout << "YES\n";
	else
		cout << "NO\n";

}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}