自动搬运

查看原文

来自洛谷，原作者为

	CYZZ 能卷是一种幸运

搬运于2025-08-24 22:46:41，当前版本为作者最后更新于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");
    }
}

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