蓝桥账户中心

题意

n架飞机要降落  每架飞机能在[t[i],t[i]+d[i]]的时刻区间内降落   降落需要l[i]的时间

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落

判断这些飞机能否全部降落

1≤𝑇≤10，1≤𝑁≤10，0≤𝑇𝑖,𝐷𝑖,𝐿𝑖≤105。

方法一 全排列

思路:

数据很小

枚举降落顺序 直接用next_permutation

每个飞机有一个可降落时刻的区间[t[i],t[i]+d[i]] 降落耗时l[i]

维护now变量  记录上一架飞机降落结束的时间  当前飞机能在now之后开始降落

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);}
void cmin(int &a,int b){a=min(a,b);}
const int N=20,MOD=1e9+7,INF=0x3f3f3f3f,LINF=LLONG_MAX;
int t[N],d[N],l[N],n;
pii p[N];
int per[N];
/*
枚举降落顺序 
每个飞机有一个可降落时刻的区间[t[i],t[i]+d[i]] 降落耗时l[i]
维护now变量记录当前能在now之后开始降落

*/
bool check(){
    int now=0;
    for(int i=1;i<=n;i++){
        int idx=per[i];
        if(now>p[idx].second) return 0;
        if(now<=p[idx].first) {
            now=p[idx].first;
        }
        now+=l[idx];
    }
    return 1;
}
void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>d[i]>>l[i];
    for(int i=1;i<=n;i++){
        p[i]={t[i],t[i]+d[i]};
    }
    
    for(int i=1;i<=n;i++) per[i]=i;
    do
    {
        if(check()){
            cout<<"YES"<<endl;
            return;
        }
    } while (next_permutation(p+1,p+1+n));
    cout<<"NO"<<endl;
    
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t=1;
    cin>>t;
    while (t--) solve();

}

方法二 DFS

思路:

来自 [蓝桥杯]真题讲解：飞机降落（DFS枚举）_蓝桥杯飞机降落-CSDN博客

开一个状态数组 记录当前这架飞机有没有降落过

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);}
void cmin(int &a,int b){a=min(a,b);}
const int N=20,MOD=1e9+7,INF=0x3f3f3f3f,LINF=LLONG_MAX;
int t[N],d[N],l[N],n;
pii p[N];
bool st[N];

bool dfs(int idx,int now){//idx表示当前有idx个飞机成功降落   now表示上一架飞机降落结束的时刻
    if(idx>=n) return 1;

    for(int i=1;i<=n;i++){
        if(st[i]) continue;

        auto [ll,rr]=p[i];
        if(now>rr) {
            return 0;//now只会变大  所以这个飞机一定降落不了  直接return 0
        }

        //这个飞机能降落 先标记为1  
        st[i]=1;

        int t=max(ll,now)+l[i];
        if(dfs(idx+1,t)) return 1;//宏观地看 如果后面所有的飞机都成功降落 就返回1

        //这个方案不成功 所以在这一步撤销选择 把st[i]重置为0
        st[i]=0;

    }
    return 0;
}

void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>d[i]>>l[i];
    for(int i=1;i<=n;i++){
        p[i]={t[i],t[i]+d[i]};
    }
    memset(st,0,sizeof st);
    if(dfs(0,0)){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
   
    
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t=1;
    cin>>t;
    while (t--) solve();

}

具体看注释

关于now>rr时return 0：

return 0就是剪枝了 其实continue也可以 但是速度慢一些

可以证明 now只会变大 当前now都比rr大了 往后递归now永远比rr大 所以这架飞机一定没法降落 所以这种方案直接return 0就行了

另外多组数据 记得初始化st数组