``` #include <bits/stdc++.h> using namespace std; int N, flag, vis[11] = { 0 }; int a[11], b[11], c[11]; void dfs(int num, int cnt, int time)//time表示飞机降落的最早时间 { if (cnt == num+1) flag=1;//当所有飞机安排成功，cnt=num+1 for (int i = 1; i <= num; i++) { if (!vis[i] && a[i] + b[i] >= time)//到达时间＋盘旋时间>=time才能够降落 { //分情况： //1：上一架飞机降落完成，下一架飞机还没有到，则time=a[i]+c[i] //2：上一架飞机还没降落完成，下一架飞机已经到了,time=time+c[i] vis[i] = 1; dfs(num, cnt + 1, max(time, a[i]) + c[i]); vis[i] = 0; } } } int main() { int K; cin >> K; while (K--) { cin >> N; for (int i = 1; i <= N; i++) cin >> a[i] >> b[i] >> c[i]; flag = 0; vis[N] = { 0 }; dfs(N, 1, 0); if (flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0; } ```

搜索 ``` #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; } ```

``` #include<bits/stdc++.h> using namespace std; const int N=15; int n,t; int a[N][3]; bool st[N]; bool flag; void dfs(int u,int last) { if(u>=n) flag=1; if(flag) return; for(int i=1;i<=n;i++) { if(!st[i])//检查没降落的飞机 { //如果上一架飞机降落的时间大于当前飞机的到达时间和盘旋时间,则该飞机无法降落直接return if(last>a[i][0]+a[i][1]) return; //飞机标记降落 st[i]=true; //如果上一架飞机降落时间小于当前飞机到达时间，则可以降落 if(last<a[i][0]) { dfs(u+1,a[i][0]+a[i][2]); } else //如果上一架飞机降落时间大于或者等于当前飞机降落时间，则应该等上一架飞机降落后降落 dfs(u+1,a[i][2]+last); //恢复现场 st[i]=false; } } } int main() { cin>>t; for(int i=1;i<=t;i++) { memset(st,0,sizeof st); flag=0; cin>>n; for(int j=1;j<=n;j++) { cin>>a[j][0]>>a[j][1]>>a[j][2]; //对应t,d,l } dfs(0,0); if(flag) puts("YES"); else puts("NO"); } return 0; } ```

``` ` #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,flag,st[N]; struct plane{ int early; int late; int t; }a[N]; void dfs(int x,int now){ if(flag) return; if(x>n){ flag=1; cout<<"YES"<<endl; return; } for(int i=1;i<=n;i++){ if(!st[i]){ if(a[i].late<now) return; st[i]=1; dfs(x+1,max(a[i].early,now)+a[i].t); st[i]=0; } } } int main() { int T; cin>>T; while(T--){ n=0; flag=0; cin>>n; for(int i=1;i<=n;i++){ int d,b,c; cin>>d>>b>>c; a[i].early=d; a[i].late=d+b; a[i].t=c; } dfs(1,0); if(!flag) cout<<"NO"<<endl; } return 0; } ``` `

``` #include <iostream> #include <vector> #include <algorithm> using namespace std; struct Airplane { int T; int D; int L; }; bool backtrack (vector<Airplane>& planes, vector<bool>& used, int index, int currentTime) { if (index == planes.size()) { return true; } for (int i = 0; i < planes.size(); i++) { if (!used[i]) { int earliest = max(currentTime, planes[i].T); int latest = planes[i].T + planes[i].D; if (earliest <= latest) { used[i] = true; if (backtrack(planes, used, index + 1, earliest + planes[i].L)) { return true; } } used[i] = false; } } return false; } bool canAllLand (vector<Airplane>& planes) { int n = planes.size(); vector<bool> used(n, false); return backtrack(planes, used, 0, 0); } int main() { int t, N; cin >> t; for (int i = 0; i < t; i++) { cin >> N; vector<Airplane> planes(N); for (int j = 0; j < N; j++) { cin >> planes[j].T >> planes[j].D >> planes[j].L; } if (canAllLand(planes)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; } ```

``` #include<bits/stdc++.h> using namespace std; struct air{ int t; int d; int l; bool used; }; air plane[10]; bool canfly; void DFS(int n, int t, int cnt){ int nextt; for(int i = 0; i < n; i++){ if(plane[i].used) continue;//排除飞过的 if(t > (plane[i].t + plane[i].d)) break;//如果时间已经超过某架飞机的落地极限，循环直接结束 if(plane[i].t > t) nextt = plane[i].t;//如果下一个飞机还没到，就直接跳到下个飞机来的时间 else nextt = t; plane[i].used = true; DFS(n, nextt + plane[i].l, cnt + 1); plane[i].used = false; } if(cnt == n) canfly = true; } int main(){ int t; cin>>t; for(int i = 0; i < t; i++){ int n; cin>>n; canfly = false; for(int j = 0; j < n; j++){ cin>>plane[j].t>>plane[j].d>>plane[j].l; plane[j].used = false; } DFS(n, 0, 0); if(canfly) printf("YES\n"); else printf("NO\n"); } } ```

``` #include<bits/stdc++.h> using namespace std; int T, N; struct plane { int T; // 到达机场上空的时刻 int D; // 能继续盘旋的时间 int L; // 降落过程需要的时间 }; plane a[20]; int vis[20] = {0}; int flag = 0; // 标志位，表示是否能成功降落 void dfs(int x, int time) { if(x > N) { flag = 1; } if(flag) { return; } for(int i = 1; i <= N; i++) { if(!vis[i]) { if(a[i].T + a[i].D < time) { return; } vis[i] = 1; dfs(x+1, max(time, a[i].T) + a[i].L); vis[i] = 0; } } } int main() { cin >> T; while(T--) { cin >> N; flag = 0; for(int i = 1; i <= N; i++) { cin >> a[i].T >> a[i].D >> a[i].L; } dfs(1,0); if(flag == 1) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; } ```

``` #include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct palne{ int t,d,l; }pl[12]; int flagpl[12]; int flag=0; void dfs(int top,int len,int nowtime){ if(top==len){ flag=1; return; } for(int i=0;i<len;++i){ if(flag==1) return; //为了节省不必要的递归，找到了一种方案就直接退出 if(flagpl[i]!=1&&nowtime<=pl[i].t+pl[i].d){ flagpl[i]=1; if(nowtime<pl[i].t) dfs(top+1,len,pl[i].t+pl[i].l); else dfs(top+1,len,nowtime+pl[i].l); flagpl[i]=0; } } return ; } int main(){ int k; int n; cin>>k; for(int i=0;i<k;i++){ cin>>n; for(int j=0;j<n;++j) cin>>pl[j].t>>pl[j].d>>pl[j].l; flag=0; dfs(0,n,0); if(flag==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } ```

``` #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; } ```

``` #include <iostream> using namespace std; const int N = 15; int t, n, num, idx; int T[N], D[N], L[N],q[N]; bool st[N]; void dfs(int x) { if (x > n) { for (int i = 1; i <= n; i ++ ) { if (i == 1) num = T[q[i]] + L[q[i]]; else { if (num > T[q[i]] + D[q[i]]) return ; num += L[q[i]]; } } idx ++ ; return ; } for (int i = 1; i <= n; i ++ ) { if (!st[i]) { q[x] = i; st[i] = true; dfs(x + 1); st[i] = false; } } return ; } int main() { cin >> t; while (t -- ) { idx = 0; num = 0; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> T[i] >> D[i] >> L[i]; dfs(1); if (idx >= 1) cout << "YES"; else cout << "NO"; cout << endl; } return 0; } ```