深度优先搜索

/*两种写法，本质都是全排列，第一种是手写深搜，第二种是用next_permutation找下一个排列，第二种相对更好写也更好理解一点*/
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

/*飞机结构*/
//earlyt为最早降落时间，latet为最晚降落时间（最早降落时间+盘旋时间），lt为降落需要的时间，重定义小于符号以便将所有飞机按最早降落时间排序以提高性能
struct plane {
	int earlyt;
	int latet;
	int lt;
	plane(int a, int b, int c) :earlyt(a), latet(b), lt(c) {};
	bool operator<(plane& t) {
		if (earlyt < t.earlyt)
			return true;
		else return false;
	}
};

//n为飞机架数
int n;
//maxt记录所有飞机的最晚降落完成时间，用于剪枝，mint为记录最早降落飞机的时间，为深搜的起点，tar为是否找到方案的标记
int maxt = 0, mint = 100000;
bool tar = false;

/*判断是否所有飞机都降落完成*/
bool judge(vector<bool>& finish) {
	for (bool i : finish) {
		if (!i)
			return false;
	}
	return true;
}

/*获得未起飞的飞机中的最晚降落时间的最小值*/
//若当前时间比该最小值还大则说明至少有一架飞机无法降落，可以剪枝
int getmint(vector<bool>& finish, vector<plane> planes) {
	int mt = 10000000;
	for (int i=0;i<finish.size();i++)
		if (!finish[i]) {
			mt = min(mt, planes[i].latet);
		}
	return mt;
}

/*深度优先搜索，finish为飞机是否降落的记录，timen为当前时间*/
void dfs(vector<bool>& finish,int timen,vector<plane>& planes) {
    //当所有飞机都降落完成时，令标记为真，记录结果
	if (judge(finish)) {
		tar = true;
		return;
	}
	//三种剪枝情况：1.已经找到解决方案  2.当前时间已经比最晚时间还晚 3.当前已经有飞机无法降落
	if (tar||timen>maxt||timen>getmint(finish,planes))
		return;
	for (int j = 0; j < n; j++) {
		if (!finish[j]) {
			//当前时间合法时令其降落
			if (planes[j].earlyt <= timen && planes[j].latet >= timen) {
				finish[j] = true;
				dfs(finish,timen+planes[j].lt,planes);
				//回溯
				finish[j] = false;
			}
			//由于飞机降落时间并不连续，当前时间若过早时将时间跳转至该飞机的最早时间
			else if (planes[j].earlyt > timen) {
				dfs(finish,planes[j].earlyt,planes);
			}
		}
	}

}

int main()
{
	int ct;
	cin >> ct;
	for (int i = 0; i < ct; i++) {
		vector<plane> planes;
		cin >> n;
		mint = 50000, maxt = 0;
		for (int i = 0; i < n; i++) {
			int tmpa, tmpb, tmpc;
			cin >> tmpa >> tmpb >> tmpc;
			mint = min(tmpa, mint);
			maxt = max(tmpa + tmpb+tmpc, maxt);
			plane tmp(tmpa, tmpa + tmpb, tmpc);
			planes.push_back(tmp);
		}
		vector<bool> finish(n, false);
		sort(planes.begin(), planes.end());
		dfs(finish, mint, planes);
		if (tar) {
			cout << "YES" << endl;
		}
		else
			cout << "NO" << endl;
		tar = false;
	}
	return 0;
}

/*第二种写法*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct plane {
	int earlyt;
	int latet;
	int lt;
	plane(int e, int l, int ltn) :earlyt(e), latet(l), lt(ltn) {};
};

bool cmd(plane& a, plane& b) {
	if (a.earlyt < b.earlyt)
		return true;
	else if (a.earlyt == b.earlyt && a.latet < b.latet)
		return true;
	else return false;
}

int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		vector planes;
		for (int j = 0; j < n; j++) {
			int e, l, lt;
			cin >> e >> l >> lt;
			l += e;
			planes.push_back(plane(e, l, lt));
		}
		sort(planes.begin(), planes.end(), cmd);
		int te = planes[0].earlyt;   //记录最早时间
		bool tar0 = false;   //记录是否找到答案，用于NO判断
		do {
			bool tar = true;  //记录是否找到答案，用于yes判断
			long long timen = te;
			for (int i = 0; i < planes.size(); i++) {
				if (timen < planes[i].earlyt)
					timen = planes[i].earlyt;
				if (timen > planes[i].latet) {
					tar = false;
					break;
				}
				timen += planes[i].lt;
			}
			if (tar)
			{
				tar0 = true;
				cout << "YES\n";
				break;
			}
		} while (next_permutation(planes.begin(), planes.end(), cmd));
		if (!tar0)
			cout << "NO\n";
	}
	return 0;
}