飞机降落
原题链接
飞机降落
解题思路一(dfs 剪枝)
- 可以用暴搜 dfs 剪枝来解决
- dfs 两个参数,分别为
- u 目前已经有 u 架飞机完成了停靠
- last_time 完成停靠的时间为 last_time
- 判断条件为若 last_time 小于等于该飞机的 t + d 则可以完成停靠
- 若后面的飞机不能完成停靠则剪枝
时间复杂度 $O(n!)$
C ++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 11;
struct data
{
int t, d, l;
}p[N];
int n;
bool st[N];
bool dfs(int u, int last_time)
{
if (u == n) return true;
for (int i = 0; i < n; i ++ )
{
auto k = p[i];
// 判断如果该飞机还未停靠 且 还未超过该飞机可停靠时间(t + d)
if (!st[i] && last_time <= k.t + k.d)
{
st[i] = true;
if (dfs(u + 1, max(last_time, k.t) + k.l)) return true;
// 下一架飞机最早在其 t 时刻起飞,但是必须在上一架飞机完成停靠后起飞
// 判断后面的飞机是否可以停靠
st[i] = false;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t -- )
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
int t, d, l;
cin >> t >> d >> l;
p[i] = {t, d, l};
}
memset(st, 0, sizeof st);
if (dfs(0, 0)) puts("YES");
else puts("NO");
}
return 0;
}
解题思路二(状态压缩 dp)
- 状态表示为 f[i, j]
- i 是一个二进制数,表示全部飞机是否停靠的状态,停靠完成为 1,未停靠为 0
- j 是最后一架停靠的飞机
- f[i, j] 表示完成 i j 停靠状态的最短时间
- 状态转移方程
- j 前一驾停靠的飞机为 k ,状态表示为 f[i - (1 << j)][k]
- 方程:f[i, j] = min(f[i, j], max(f[i - (1 << j), k], j.t) + j.l)
时间复杂度 $n^2$
#include <iostream>
#include <cstring>
using namespace std;
const int N = 11, M = 1 << N;
struct data
{
int t, d, l;
}p[N];
int f[M][N];
int t, n;
bool flag;
int main()
{
ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
cin >> t;
while (t -- )
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
int t, d, l;
cin >> t >> d >> l;
p[i] = {t, d, l};
}
memset(f, 0x3f, sizeof f);
for (int i = 0; i < n; i ++ ) f[1 << i][i] = p[i].t + p[i].l;
for (int i = 1; i < 1 << n; i ++ )
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
for (int k = 0; k < n; k ++ )
if ((i - (1 << j)) >> k & 1)
{
auto q = f[i - (1 << j)][k];
if (p[j].t + p[j].d >= q) f[i][j] = min(f[i][j], max(p[j].t, q) + p[j].l);
}
flag = false;
for (int i = 0; i < n; i ++ )
if (f[(1 << n) - 1][i] != 0x3f3f3f3f)
{
flag = true;
break;
}
if (flag) puts("YES");
else puts("NO");
}
return 0;
}