返回题解分享
讨论 / 题解分享/ 帖子详情

飞机降落(编程题) - 题解

#include<bits/stdc++.h>
using namespace std;
const int N=15;


int n,t;
int a[N][3];
bool st[N];
bool flag;

void dfs(int u,int last)
{
    if(u>=n)
        flag=1;
    if(flag)
        return;
    for(int i=1;i<=n;i++)
    {
        if(!st[i])//检查没降落的飞机
        {
            //如果上一架飞机降落的时间大于当前飞机的到达时间和盘旋时间,则该飞机无法降落直接return
            if(last>a[i][0]+a[i][1]) return;
            //飞机标记降落
            st[i]=true;
            //如果上一架飞机降落时间小于当前飞机到达时间,则可以降落
            if(last<a[i][0])
            {
                dfs(u+1,a[i][0]+a[i][2]);
            }
            else
                //如果上一架飞机降落时间大于或者等于当前飞机降落时间,则应该等上一架飞机降落后降落
                dfs(u+1,a[i][2]+last);
            //恢复现场
            st[i]=false;
        }
    }
}

int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        memset(st,0,sizeof st);
        flag=0;
        cin>>n;
        for(int j=1;j<=n;j++)
        {
            cin>>a[j][0]>>a[j][1]>>a[j][2];
            //对应t,d,l
        }
        dfs(0,0);
        if(flag)
            puts("YES");
        else
            puts("NO");
    }
    

    return 0;
}
0 回复 0 转发 1 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!