题目描述

Jack 经营一个特殊的飞机停车场，这个停车场非常狭窄，飞机只能按照**后进先出（LIFO）**的方式进出，类似于栈的操作。每架飞机有一个预定的到达时间 $S_i$ 和离开时间 $T_i$。

由于停车场的LIFO特性，不是所有的停车请求都能被满足。题目要求找出最多能停放多少架飞机。

输入格式

• 第一行：测试用例数 $T$ ($1\le T\le 5$)
• 每个测试用例：
  • 第一行：飞机数 $N$ ($1\le N\le 300$)
  • 接下来 $N$ 行：每行两个整数 $S_i$ 和 $T_i$ ($0\le S_i<T_i\le 10^9$)

输出格式

对于每个测试用例，输出一个整数，表示最多能停放的飞机数量。

样例

输入：

2
4
1 10
2 5
3 7
6 9
3
10 12
10 15
13 17

输出：

3
2

算法分析

问题难点

由于LIFO约束，两个飞机的时间区间如果相交但不包含，则它们不能同时停放。例如：

• 区间 [2,5] 和 [3,7] 相交但不包含，不能同时停放
• 区间 [1,10] 和 [2,5] 是包含关系，可以同时停放

核心思路

这是一个经典的区间调度问题，可以使用离散化 + 区间动态规划解决。

1. 离散化处理

由于时间范围很大（最大 $10^9$），但实际使用的时间点最多只有 $2N=600$ 个，因此需要将时间点映射到小范围的整数。

2. 区间DP定义

设 $dp[i][j]$ 表示在离散化后的时间区间 $[i,j]$ 内最多能停放的飞机数量。

3. 状态转移

对于区间 $[i,j]$，考虑以下几种情况：

• 不选择任何以 $i$ 开始或以 $j$ 结束的飞机：$dp[i][j]=\max (dp[i+1][j],dp[i][j-1])$
• 选择一架时间区间正好是 $[i,j]$ 的飞机：$dp[i][j]=\max (dp[i][j],cnt[i][j])$
• 枚举分割点 $k$：$dp[i][j]=\max (dp[i][j],dp[i][k]+dp[k][j]+cnt[i][j])$

其中 $cnt[i][j]$ 表示时间区间正好是 $[i,j]$ 的飞机数量。

算法正确性证明

区间DP能够正确处理LIFO约束的原因：

1. 包含关系：如果区间A包含区间B，那么B必须先于A进出，这在栈中是可以实现的
2. 不相交区间：完全不相交的区间不会相互影响
3. 相交但不包含：这种情况在DP过程中会被自然排除，因为无法找到合适的分割点使得两个区间都能被包含

时间复杂度

• 离散化：$O(N\log N)$
• 区间DP：$O(M^3)$，其中 $M\le 2N=600$
• 总体复杂度：$O(N^3)$，对于 $N\le 300$ 是可接受的

AC代码

// Airplane Parking
// UVa ID: 1255
// Verdict: Accepted
// Submission Date: 2025-10-10
// UVa Run Time: 0.100s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char* argv[]) {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<pair<int, int>> planes(n);
        vector<int> times;
        // 读取输入并收集所有时间点
        for (int i = 0; i < n; i++) {
            cin >> planes[i].first >> planes[i].second;
            times.push_back(planes[i].first);
            times.push_back(planes[i].second);
        }
        // 离散化
        sort(times.begin(), times.end());
        times.erase(unique(times.begin(), times.end()), times.end());
        int sz = times.size();
        map<int, int> comp;
        for (int i = 0; i < sz; i++) {
            comp[times[i]] = i;
        }
        // 初始化计数数组
        vector<vector<int>> cnt(sz, vector<int>(sz, 0));
        for (int i = 0; i < n; i++) {
            int start = comp[planes[i].first];
            int end = comp[planes[i].second];
            cnt[start][end]++;
        }
        // 区间DP
        vector<vector<int>> dp(sz, vector<int>(sz, 0));
        for (int len = 2; len <= sz; len++) {
            for (int i = 0; i + len <= sz; i++) {
                int j = i + len - 1;
                // 初始值：当前区间端点对应的飞机数量
                dp[i][j] = cnt[i][j];
                // 枚举分割点
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + cnt[i][j]);
                }
                // 也考虑不包含端点飞机的情况
                dp[i][j] = max(dp[i][j], dp[i + 1][j]);
                dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            }
        }
        cout << dp[0][sz - 1] << '\n';
    }
    return 0;
}

总结

本题的关键在于将LIFO约束转化为区间包含关系的约束，然后使用区间动态规划求解。离散化技巧有效地处理了大范围的时间数据，使得算法在合理的时间内完成计算。

这种区间DP的方法具有通用性，可以应用于其他具有类似约束的调度问题。