题目数据比较小n<=10 可以直接爆搜 // n ! * n = 3e8 <1e10
t 到 t+l 区间有长度是 d 的浮动 默认在最左边
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n; 4 bool st[15]; 5 struct plane 6 { 7 int t,d,l; 8 }p[15]; 9 bool dfs(int u, int last)//全排列线段找符合；u表示计数，last表示前一个飞机下落时间 10 { 11 if (u == n) return true; 12 13 for (int i = 0; i < n; i ++ ) 14 { 15 int t = p[i].t, d = p[i].d, l = p[i].l; 16 if (!st[i] && t + d >= last)//下一个飞机下落时间晚于前一个 17 { 18 st[i] = true; 19 if (dfs(u + 1, max(last, t) + l)) 20 return true; 21 st[i] = false; 22 } 23 } 24 25 return false; 26 } 27 int main() 28 { 29 int T;cin>>T; 30 while(T--) 31 { 32 cin>>n; 33 for(int i=0;i<n;i++) 34 { 35 int t,d,l;cin>>t>>d>>l; 36 p[i]={t,d,l}; 37 } 38 memset(st , false ,sizeof st); 39 if(dfs(0,0)) cout<<"YES"<<endl; 40 else cout<<"NO"<<endl; 41 } 42 return 0; 43 }