威海市住房和城乡建设局网站,怎么制作应用软件,手机网站cms 下载,咨询服务类公司这道题本来作者以为是可以用一些小技巧进行暴力解法的#xff0c;但是后来试了一下#xff0c;不能过去全部数据。
下面是对半个的题解#xff1a;
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath…这道题本来作者以为是可以用一些小技巧进行暴力解法的但是后来试了一下不能过去全部数据。
下面是对半个的题解
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#includesstream
#includemap
#includelimits.h
#includeset
#define MAX 105
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
int n, m, counts0;
LL A, B;
int res 0;
struct fly {int times;int pan_xuan;int down;
};
fly a[MAX];
bool cmp(fly a, fly b) {return a.times a.pan_xuan b.times b.pan_xuan;
}
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin n;int i 0;while (n--){i 0;cin m;while (m--) {int t, d, l;cin t d l;a[i].times t;a[i].pan_xuan d;a[i].down l;i;}sort(a, a i, cmp);int flag 1;int sum 0;_for(j, 0, i) {if (j 0)sum a[j].times a[j].down;else {if (sum a[j].times a[j].pan_xuan) {sum a[j].down;}else{flag 0;break;}}}if (flag)cout YES endl;elsecout NO endl;}return 0;
}
作者这里犯了一个错误每一个飞机都有可能是第一个降落的飞机作者一开始认为是时刻上谁最早谁就先降落结果并不是那个样子。后面的大体思路其实是正确的。
那么后来就与大佬们讨论一下发现这个题也是一道DFS的暴力题。
OK废话不多说那就开始;
注意这里作者认为方便的话可以定义结构体进行题解。如果我们开3个数组处理起来会很麻烦。
1.我们看到有飞机到达的时刻和盘旋的时间也就是可以等待的时间最后就是降落的时间。我们可以得出来什么结论呢刚开始我们就可以知道飞机的最早降落时间和最晚降落时间最早降落时间就是它到达飞机场的时刻最晚降落时间就是到达时刻加上盘旋的时间只要飞机在这个时间段之内就可以降落也就是说如果第i架飞机想要降落首先需要知道前面得i-1架飞机降落后总共用到的时间。如果说是在这个时间范围里那么这个飞机就可以降落否则不行。
2.我们开始考虑。因为每一架飞机都有可能是第一架飞机的降落所以这就涉及到一个排序问题了。也就是说我们可以把这个问题转化为排序型递归的题目。那么就需要有一个状态函数来判断是否选过这个飞机。OK那么我们套上模板。终止条件就是当我们遍历到最后一架飞机的时候就可以说是YES了。
有人问不对呀不应该是大于飞机的架数才可以吗假设我们需要降落三架飞机如果前两架都已经降落了我们还需要再判断第三架吗因为第三架都已经是最后一架飞机了所以我们直接就可以认为这种可能性是可以的。
3.不要忘记我们只是对于一个飞机深度搜索我们需要从每一个飞机为起点这样才能覆盖到所有可能性。
注意在dfs函数中将要进行递归的时候我用了一个if else语句。这里为什么这样判断呢你想一下如果说我们前几架飞机的降落时间还没有下一架飞机的开始时刻多那么也就是说我们需要等到下架飞机最早下降的时刻才能进行降落如果说在下一架飞机的那个允许时间范围内我们就可以直接接着刚刚已经用过的时间加上下架飞机的降落时间了。
上代码
#includeiostream
#includestdio.h
#includecstring
#includecstdlib
#includecmath
#includevector
#includealgorithm
#includestack
#includequeue
#includesstream
#includemap
#includelimits.h
#includeset
#define MAX 15
#define _for(i,a,b) for(int ia;i(b);i)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
int n, m, counts0;
LL A, B;
int res 0;
int st[MAX];
bool flag false;
struct fly {int times;int pan_xuan;int down;
};
fly a[MAX];
void dfs(int nums, int times) {if (nums m) {flag true;return;}for (int i 1; i m; i) {if (!st[i] times a[i].times a[i].pan_xuan)return;if (!st[i] times a[i].times a[i].pan_xuan) {st[i] 1;if (a[i].times times)dfs(nums 1, a[i].times a[i].down);elsedfs(nums 1, times a[i].down);st[i] 0;}}
}
int main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin n;while (n--) {cin m;flag false;_for(i, 1, m 1) {cin a[i].times a[i].pan_xuan a[i].down;}_for(j, 1, m 1) {st[j] 1;dfs(1, a[j].times a[j].down);st[j] 0;}if (flag)cout YES endl;elsecout NO endl;}return 0;
}
