Silwan


私信TA

用户名:uq_82610599714

访问量:6818

签 名:

等  级
排  名 6449
经  验 1416
参赛次数 0
文章发表 8
年  龄 0
在职情况 学生
学  校 哈尔滨工业大学(深圳)
专  业 计算机专业

  自我简介:

解题思路:
由于N<10,这个数据很小,把所有可能的顺序都列一遍,每次贪心的使得前一架飞机降落时间最早。如果有一种方案满足,那么就是YES

注意事项:

参考代码:

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define getl(s) getline(cin,s)
#define max(a,b) a > b ? a : b
#define min(a,b) a < b ? a : b
#define abs(a)   a > 0 ? a : -a
#define lowbit(a) a & -a
using namespace std;
const int M = 12;
int n,t[M],d[M],l[M];
bool st[M],ans = false;
void dfs(int m,int r,int now)//分别代表飞机的总数,排序中前一家飞机的降落时间,本次排哪一架飞机
{
	if(t[now] + d[now] < r)return ;//如果前一架飞机的降落时间在本次飞机最晚降落时间之后,那么就排除这种情况
	int res;//代表本次飞机可能降落的最早时间
	if(t[now] >= r)res = t[now] + l[now];
	else res = r + l[now];
	bool flag = true;//是否已经排列完所有的飞机
	for(int i = 1;i <= m;i++)
	{
		if(st[i])continue;	
		flag = false;//还有飞机没排完
		st[i] = true;
		dfs(m,res,i);
		st[i] = false;
	}
	if(flag)ans = true;
		
}
void solve()
{
	ans = false;
	memset(st,false,sizeof(st));
	int m;cin>>m;
	for(int i = 1;i <= m;i++)
		cin>>t[i]>>d[i]>>l[i];
	for(int i = 1;i <= m;i++)
	{
		st[i] = true;
		dfs(m,0,i);
		st[i] = false;
	}	
	if(ans)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	while(n--)solve();
	return 0;
}


 

0.0分

15 人评分

  评论区

  • «
  • »