飛機降落（DFS）

藍橋杯2023年第十四屆省賽真題-飛機降落 - C語言網 (dotcpp.com)

一開始我是真的沒想到用DFS做，我還在想用什么策略排序呢。需要再刷！！！

雙馬尾的意思其實是刷了兩次...

一刷：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//這道題是真的牛逼。他沒有策略，而是用DFS遍歷所有情況，然后判斷每一種情況可不可行，
//如果所有的都不可行，那就說明總的不可行
//真的無腦我去struct Plane
{int t;	//到達時間int d;	//盤旋時間int l;	//降落時間
};int n, cnt;vector<Plane>flys;
vector<int>visit(11);	//記錄bool DFS(int num,int last)	//已經降落的數量  最后降落時間
{if (num==cnt)return true;for (int i = 0; i < cnt; i++){if (visit[i] == 0 && last <= flys[i].t + flys[i].d){visit[i] = 1;//現在的last應該是最近能降落的時間+降落持續時間if (DFS(num + 1, max(last, flys[i].t) + flys[i].l))	//如果之后的所有情況都可以實現return true;visit[i] = 0;}}return false;
}int main()
{cin >> n;int t, d, l;for(int i=0;i<n;i++){cin >> cnt;flys.clear();for (int i = 0; i < 11; i++)visit[i] = 0;for(int j=0;j<cnt;j++)	//輸入數據{cin >> t >> d >> l;flys.push_back({ t,d,l });}if (DFS(0,0))	cout << "YES" << endl;else    cout << "NO" << endl;}return 0;
}

二刷：

雖然同樣是用DFS，但是這次策略有所不同：一旦得到一個解，那就咔咔全部返回，直接輸出，比之前的快了不少。

//飛機降落
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;struct Time
{int t,d,l;	//到達時間，最大盤旋時間，降落時間 };int n,m; 
Time plane[11];
int book[11];bool dfs(int last,int cnt)	//last 上一趟飛機結束時間  cnt當前已經遍歷過的飛機數 
{if(cnt==m)	return true;for(int i=0;i<m;i++)	//遍歷所有的飛機，作為下一趟 {Time nex=plane[i];if(last>nex.t+nex.d || book[i]==1)	continue;	//如果時間不合適或者已經標記過，不行 book[i]=1;if(dfs(max(last,nex.t)+nex.l,cnt+1))	return true;book[i]=0;	//回溯 } return false;	//所有方案都不行 
}int main()
{cin>>n;while(n--){cin>>m;memset(book,0,sizeof(book));memset(plane,0,sizeof(plane));for(int i=0;i<m;i++)cin>>plane[i].t>>plane[i].d>>plane[i].l;if(dfs(0,0))	cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;}