AcWing 4957. 飞机降落
原题链接
简单
dfs
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10 + 20;
int n;
struct plane
{
int t, d, l;
}p[N];
bool st[N]; // 判断当前飞机是否降落
//u表示已经有U架飞机成功降落了。
//time表示当前的时间,前一架飞机落地的时间。
bool dfs(int u, int time)
{
if(u >= n) return true;
//考虑第(u + 1)架飞机谁落。
for(int i = 0; i < n; i ++)
{
if(!st[i])
{
st[i] = true;
if(p[i].t + p[i].d < time)
{
//不能成功降落
st[i] = false;
return false;
}
int t = max(time, p[i].t) + p[i].l;
if(dfs(u + 1, t))
return true;
st[i] = false;
}
}
return false;
}
signed main()
{
int t;
cin >> t;
while(t --)
{
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;
}
}