本文主要是介绍【2024.1.20练习】D: 飞机降落，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
D: 飞机降落（10分）
问题描述
略
我的代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 11;
int T;
int n;
int t[max_n];
int d[max_n];
int l[max_n];
bool f[max_n];
int v;int dfs(int t0, int n0) {if (t0 > t[n0] + d[n0]) {return 0;}if (t0 < t[n0]) {t0 = t[n0];}t0 += l[n0];v++;if (v == n + 1) {f[n0] = true;return 1;}f[n0] = true;for (int i = 1; i <= n; i++) {if (f[i] = false) {if (dfs(t0, i)) {return 1;}}}return 0;
}int main() {t[0] = 0;d[0] = 0;l[0] = 0;cin >> T;while (T--) {v = 0;cin >> n;for (int j = 0; j <= n; j++) {f[j] == false;}for (int i = 1; i <= n; i++) {cin >> t[i] >> d[i] >> l[i];}if (dfs(0,0)) {cout << "YES" << endl;}else {cout << "NO" << endl;}}return 0;
}由于输入数量小，使用暴力搜索为O(10!)不会超时。
这段代码样例测试成功，但是无法通过。原因很简单，在递归函数中使用了全局变量的自增，内层递归结束进入前一层递归时，全局变量并不会回退成上一层的，不像递归函数参数具有回溯性。
修改后的代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 11;
int T;
int n;
int t[max_n];
int d[max_n];
int l[max_n];
bool f[max_n];
int v;int dfs(int t0, int n0, int v0) {if (t0 > t[n0] + d[n0]) {return 0;}//未通过if (t0 < t[n0]) {t0 = t[n0];}t0 += l[n0];//通过检测v0++;if (v0 == n + 1) {return 1;}for (int i = 1; i <= n; i++) {if (f[i] == false) {f[i] = true;if (dfs(t0, i, v0)) {return 1;}f[i] = false;}}return 0;
}int main() {t[0] = 0;d[0] = 0;l[0] = 0;cin >> T;while (T--) {v = 0;cin >> n;for (int j = 0; j <= n; j++) {f[j] = false;}for (int i = 1; i <= n; i++) {cin >> t[i] >> d[i] >> l[i];}if (dfs(0,0,0)) {cout << "YES" << endl;}else {cout << "NO" << endl;}}return 0;
}找了2小时Bug。终于改好了QWQ
标准代码：
#include <iostream>
#include <algorithm>using namespace std;
const int N = 10;
bool st[N];
int n;
bool flag = false;
int t[N], d[N], l[N];void dfs(int u, int last) {if (flag) return;if (u == n) {flag = true;return;}for (int i = 0; i < n; i++) {if (!st[i]) {if (t[i] + d[i] >= last) {st[i] = true;if (t[i] > last) dfs(u + 1, t[i] + l[i]);else dfs(u + 1, last + l[i]);st[i] = false;} else return;}}
}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 0; i < n; i++) cin >> t[i] >> d[i] >> l[i];for (int i = 0; i < N; i++) st[i] = false;flag = false;dfs(0, 0);if (flag) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}相比我的代码更加简洁。
这篇关于【2024.1.20练习】D: 飞机降落的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
