P9241题解

IsaacX · 2023-05-07 13:25:52 · 题解

飞机降落

贪心了一下发现不好确定顺序，n\le10 的数据直接暴力 dfs 即可。

dfs 传一个 tim 参数，表示目前已经到了第 tim 个单位时间（上一个飞机的降落时间）。飞机能降落的条件是 t_i+d_i\le tim，不满足条件就跳过。

因为不能在飞机到达机场前就开始降落，所以完成降落的时间是 \max(tim,t_i)+l_i，当作参数下传。

#include <bits/stdc++.h>
using namespace std;
int t,n,bk[15];
struct plane
{
    int t,d,l;
}a[15];
bool dfs(int dep,int tim)
{
    if(dep>n)
        return 1;
    for(int i=1;i<=n;i++)
    {
        if(bk[i]||a[i].t+a[i].d<tim)//降落条件
            continue;
        bk[i]=1;
        if(dfs(dep+1,max(tim,a[i].t)+a[i].l))//记得取max
        {
            bk[i]=0;
            return 1;//有一个成功就返回1
        }
        bk[i]=0;//记得去标记
    }
    return 0;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i].t,&a[i].d,&a[i].l);
        }
        memset(bk,0,sizeof bk);//记得清空
        if(dfs(1,0))
            printf("YES\n");
        else
            printf("NO\n");
    }
}

希望本篇题解能帮到大家！