飞机降落蓝桥杯

解题思路:

// 错误点 

// vis是否需要清0,不需要,最后回溯,完成清0

// come use dw 关系

// 主要到time取max(time,come[i]) ;; //如果time < come[i] 不是不能降落而是要等到come[i]才降落

// 为什么要来了就降落;; 因为暴力搜索已经确定了降落顺序,那么如果降落,就只需考虑自己怎么降落的快,为后面提供更好的空间。

// 在已经知道降落顺序的情况下,直接降落,是最有利的情况 

// vis[i] = 1; 一定要在确认选他时再标记,提前标记然后后面出现continue是错误的 

注意事项:

// 错误点 

// vis是否需要清0,不需要,最后回溯,完成清0

// come use dw 关系

// 主要到time取max(time,come[i]) ;; //如果time < come[i] 不是不能降落而是要等到come[i]才降落

// 为什么要来了就降落;; 因为暴力搜索已经确定了降落顺序,那么如果降落,就只需考虑自己怎么降落的快,为后面提供更好的空间。

// 在已经知道降落顺序的情况下,直接降落,是最有利的情况 

// vis[i] = 1; 一定要在确认选他时再标记,提前标记然后后面出现continue是错误的 

参考代码:

#include<iostream>

using namespace std;

int t, N;

int come[3000];

int use[3000];

int dw[3000];

int ans = 0;

int vis[3000];

// 错误点 

// vis是否需要清0,不需要,最后回溯,完成清0

// come use dw 关系

// 主要到time取max(time,come[i]) ;; //如果time < come[i] 不是不能降落而是要等到come[i]才降落

// 为什么要来了就降落;; 因为暴力搜索已经确定了降落顺序,那么如果降落,就只需考虑自己怎么降落的快,为后面提供更好的空间。

// 在已经知道降落顺序的情况下,直接降落,是最有利的情况 

// vis[i] = 1; 一定要在确认选他时再标记,提前标记然后后面出现continue是错误的 

void dfs(int step , int time)

{   

if(step == N + 1)

{

ans = 1;

return;

}

for(int i = 1; i <= N; i ++)

{

if(vis[i] == 0)

{

if(time > dw[i] + come[i]) continue; // 不合法方案  

vis[i] = 1; // 标记已经降落

dfs(step + 1,max(time , come[i]) + use[i]); // 时间变化 

vis[i] = 0; // 回溯 

}

else continue;

}

}

int main()

{

   cin >> t;

   while(t -- )

   {

    cin >> N;

    ans = 0;

for(int i = 1; i <= N; i ++ )

    {

    cin >> come[i] >> dw[i] >> use[i];

}

dfs(1 , 0);

if(ans) cout << "YES" << endl;

else cout << "NO" << endl; 

   }

}