wordpress中文字体插件,福州seo网站优化,哔哩哔哩网页版缓存视频在哪里,网站建设公司行业现状记录此题提醒自己#xff0c;此类时间轴问题可以通过DFS解决 DFS不是能解决所有题吗
对于此题#xff0c;我们将降落的飞机的个数和时间轴作为DFS的形参#xff0c;这样可以节省手动回溯的过程。
并且在DFS的过程中我们要加入一些贪心策略#xff0c;否则直接爆搜有可能搜… 记录此题提醒自己此类时间轴问题可以通过DFS解决 DFS不是能解决所有题吗
对于此题我们将降落的飞机的个数和时间轴作为DFS的形参这样可以节省手动回溯的过程。
并且在DFS的过程中我们要加入一些贪心策略否则直接爆搜有可能搜不出来答案。 如果一个飞机的到达时刻加上盘旋时间能够超过或者等于上一架飞机降落后的时间那么就可以降落。
之后要再进行判断如果这个飞机的到达时间是超过了上一架飞机降落后的时间的那么就直接把t[i] l[i]当作下一层的时间否则的话把上一个飞机降落的时间加上当前飞机降落的时间当做下一层的时间。
#includeiostream
#includecstring
using namespace std;
const int N 15;struct Node {int t;int d;int l;
}a[N];
int flag 0;
int n;
bool vis[N];void dfs(int u, int time) {if (flag)return;if (u n) {flag 1;return;}for (int i 1; i n; i) {if(!vis[i]){if(a[i].t a[i].d time){vis[i] 1;if(time a[i].t)dfs(u1,time a[i].l);else dfs(u1,a[i].t a[i].l);vis[i] 0;}}}
}int main() {int t; cin t;while (t--) {memset(vis,0,sizeof vis);cin n;for (int i 1; i n; i)cin a[i].t a[i].d a[i].l;dfs(0,0);if (flag)cout YES endl;else cout NO endl;flag 0;}return 0;
}
