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

解题思路:

        刚开始看到题大家的第一思维可能是贪心，一次找到最佳下落方案，如果能下就yes,不能就no

        写这道题的时候我脑袋里想到的是洛谷的导弹拦截和最大字段和，以最晚降落时间升序排序得到的下降顺序为最佳方案（这个应该是错的因为我敲完只过了两个点）

        n只有10,所以枚举完全可以过,用深搜将每一种方案枚举出来，判断是否可以全部降落，枚举用深搜来实现

注意事项:

参考代码:

#include

#include

using namespace std;

int q;

int n;

int vis[20];

typedef struct plan{

int x;

int y;

int z;

int tt;

}plan;

plan pl[20];

int flat;

                                                                                            //这个mm是我上一架飞机降落后的时间，用来判断当前飞机开始降落的时间

void dfs(int def,int mm){                                    

if(def>n) return;

for(int i=1;i<=n;i++){

if(vis[i]) continue;

if(def==1){

mm=pl[i].x;

}

if(mm>pl[i].tt) return;

if(def==n) flat=1;

vis[i]=1;

if(pl[i].x>mm) dfs(def+1,pl[i].x+pl[i].z);//这个小细节可能会忽略到（飞机下落完毕后是否到达了下一架飞机下落的最早时间）

else dfs(def+1,mm+pl[i].z);

vis[i]=0;

int main(){

cin>>q;

while(q--){

flat=0;

cin>>n;

for(int i=1;i<=n;i++){

cin>>pl[i].x>>pl[i].y>>pl[i].z;

pl[i].tt=pl[i].x+pl[i].y;

}

dfs(1,0);                    // 初始化：第一层，降落后的时间为0

if(flat==1) cout<<"YES"<<endl;

else cout<<"NO"<<endl;

}

return 0;

}