第十四届蓝桥杯：DFS之飞机降落

这道题，由于它的数据范围是非常小的，我们可以采取暴力搜索的措施，把每种情况都枚举出来，如果有能行的情况就返回true

同时我们也要学会剪枝，如果已经确认飞机不能降落，就不要往下再展开了

1. #include <iostream>
2. #include <vector>
3. #include <cstring>
4. const int N = 30;
5. using namespace std;
7. int st[N];
8. int t[N],d[N],l[N];
9. int n,T;
10. bool dfs(int pos,int end)
11. {
12. if(pos>n)
13. {
14. return true;
15. }
16. for(int i = 1;i<=n;i++)
17. {
18. if(st[i]) continue;
19. if(end > t[i]+d[i]) continue;
20. int newend = max(end,t[i])+l[i];
21. st[i] = true;
22. if(dfs(pos+1,newend)) return true;
23. st[i] = false;
25. }
26. return false;
27. }
28. int main()
29. {
30. cin >> T;
31. while(T--)
32. {
33. memset(st,0,sizeof(st));
34. cin >> n;
35. for(int i = 1;i<=n;i++)
36. {
37. cin >> t[i] >> d[i] >> l[i];
38. }
39. if(dfs(1,0)) cout << "YES" << endl;
40. else cout << "NO" << endl;
41. }
46. return 0;
47. }

复制代码