解题思路:
由于N<10,这个数据很小,把所有可能的顺序都列一遍,每次贪心的使得前一架飞机降落时间最早。如果有一种方案满足,那么就是YES
注意事项:
参考代码:
#include <bits/stdc++.h> #define int long long #define pii pair<int,int> #define fi first #define se second #define endl "\n" #define pb push_back #define getl(s) getline(cin,s) #define max(a,b) a > b ? a : b #define min(a,b) a < b ? a : b #define abs(a) a > 0 ? a : -a #define lowbit(a) a & -a using namespace std; const int M = 12; int n,t[M],d[M],l[M]; bool st[M],ans = false; void dfs(int m,int r,int now)//分别代表飞机的总数,排序中前一家飞机的降落时间,本次排哪一架飞机 { if(t[now] + d[now] < r)return ;//如果前一架飞机的降落时间在本次飞机最晚降落时间之后,那么就排除这种情况 int res;//代表本次飞机可能降落的最早时间 if(t[now] >= r)res = t[now] + l[now]; else res = r + l[now]; bool flag = true;//是否已经排列完所有的飞机 for(int i = 1;i <= m;i++) { if(st[i])continue; flag = false;//还有飞机没排完 st[i] = true; dfs(m,res,i); st[i] = false; } if(flag)ans = true; } void solve() { ans = false; memset(st,false,sizeof(st)); int m;cin>>m; for(int i = 1;i <= m;i++) cin>>t[i]>>d[i]>>l[i]; for(int i = 1;i <= m;i++) { st[i] = true; dfs(m,0,i); st[i] = false; } if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; while(n--)solve(); return 0; }
0.0分
15 人评分
【明明的随机数】 (C++代码)浏览:834 |
分糖果 (C++代码)浏览:1537 |
简单的a+b (C语言代码)浏览:641 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:674 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:760 |
WU-格式化数据输出 (C++代码)浏览:1312 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:609 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:821 |
用筛法求之N内的素数。 (C语言代码)浏览:711 |
局部变量作函数返回值的问题浏览:1028 |