3151: 蓝桥杯2023年第十四届省赛真题-飞机降落

#include<iostream>

using namespace std;

const int N = 15;

//创建飞机结构体

struct plane {

int Ti, Di, Li;

}p[N];

bool vis[N];//判断飞机是否被选取过

int t;//用户输入的数据数

int n;//用户输入的飞机数

bool dfs(int u,int now)//表示当前已有n架飞机成功降落，上架飞机降落的时间为now

{

if (u >= n)return true;//当所有飞机都能降落时，结束递归

for (int i = 0; i < n; i++)

{

//当目前的飞机=false时，表示未降落过，可以降落;当现架飞机处于可降落状态且到达时间+下降时间>=前架飞机的降落时间时

if (vis[i] == false&& p[i].Ti + p[i].Di >= now)

{

vis[i] = true;//可以降落此飞机

//查看下一架飞机是否符合降落条件，此时已降落飞机+1，同时找到上架飞机降落的最后时间和本架飞机到达的时间谁大，找到较大值再加上下降时间

if (dfs(u + 1, max(p[i].Ti, now) + p[i].Li))

return true;//全部符合则返回true

vis[i] = false;//若不符合则回溯，使飞机重新处于可降落状态

}

}

return false;//遍历所有条件后依然没有一个符合全部降落条件则返回false，表示不能达到要求

}

int main()

{

cin >> t;//用户输入数据数

while (t--)//设置循环结束条件

{

cin >> n;//拿到飞机数

for (int i = 0; i < n; i++)//拿到所有飞机的到达时间，飞行时间，下降时间

{

int t, d, l;

cin >> t >> d >> l;

p[i] = { t,d,l };//同时赋值给结构体

}

for (int i = 0; i < n; i++)//给所有飞机赋值false，使全部处于可降落状态

vis[i] = false;

if (dfs(0, 0))cout << "YES" << endl;//当所有飞机都可下落则输出yes，反之输出no

else cout << "NO" << endl;

}

return 0;

}