题解：线段覆盖问题 - 最小删除数与方案数

解题思路

本题需要解决两个问题：

1. 找出最少需要删除多少条线段，使得剩下的线段互不重叠
2. 计算达到这个最小删除数的不同方案总数

关键思路是将线段按照右端点排序后，使用动态规划来计算最大不重叠线段数，并同时统计方案数。最小删除数即为总线段数减去最大不重叠线段数。

算法分析

1. 排序处理：

   • 将所有线段按右端点升序排序，右端点相同时按左端点升序排序
   • 这样排序后可以保证在考虑每个线段时，前面所有不重叠的线段都已经被处理过

2. 动态规划：

   • $dp[i]$表示以第$i$个线段结尾的最多不重叠线段数
   • $choices[i]$表示对应$dp[i]$的方案数
   • 状态转移方程：
     • 如果$segments[j].end \leq segments[i].start$，则可以转移
     • 当$dp[j]+1 > dp[i]$时，更新$dp[i]$和$choices[i]$
     • 当$dp[j]+1 = dp[i]$时，累加$choices[i]$

3. 复杂度分析：

   • 排序：$O(M \log M)$
   • 动态规划：$O(M^2)$
   • 总复杂度：$O(M^2)$ （对于$M \leq 80$完全可接受）

C++代码实现（带详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 线段结构体，包含起点和终点
struct Segment {
    int start;
    int end;
};

// 自定义比较函数：按右端点升序，右端点相同按左端点升序
bool compareSegments(const Segment& a, const Segment& b) {
    if (a.end != b.end) return a.end < b.end;
    return a.start < b.start;
}

// 解决问题的核心函数
pair<int, int> solve(const vector<Segment>& segments) {
    int n = segments.size();
    if (n == 0) return {0, 1};  // 边界情况：空线段集

    // 复制并排序线段
    vector<Segment> sortedSegments = segments;
    sort(sortedSegments.begin(), sortedSegments.end(), compareSegments);

    // dp[i]: 以i结尾的最大不重叠线段数
    vector<int> dp(n, 1);      
    // choices[i]: 对应dp[i]的方案数
    vector<int> choices(n, 1); 

    // 动态规划计算
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            // 检查线段j是否与线段i不重叠
            if (sortedSegments[j].end <= sortedSegments[i].start) {
                if (dp[j] + 1 > dp[i]) {
                    // 找到更优解，更新dp和choices
                    dp[i] = dp[j] + 1;
                    choices[i] = choices[j];
                } 
                else if (dp[j] + 1 == dp[i]) {
                    // 找到相同解，累加方案数
                    choices[i] += choices[j];
                }
            }
        }
    }

    // 找出最大不重叠线段数和总方案数
    int maxlap = 0, total = 0;
    for (int i = 0; i < n; ++i) {
        if (dp[i] > maxlap) {
            maxlap = dp[i];
            total = choices[i];
        } 
        else if (dp[i] == maxlap) {
            total += choices[i];
        }
    }

    // 返回最小删除数和方案数
    return {n - maxlap, total};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  // 优化输入输出

    int m;  // 线段数量
    while (cin >> m) {
        vector<Segment> s(m);
        // 读取线段数据，确保起点小于终点
        for (int i = 0; i < m; ++i) {
            cin >> s[i].start >> s[i].end;
            if (s[i].start > s[i].end) 
                swap(s[i].start, s[i].end);
        }

        // 调用求解函数
        auto result = solve(s);
        // 输出结果
        cout << result.first << " " << result.second << "\n";
    }

    return 0;
}

复杂度分析

1. 时间复杂度：

   • 排序操作：$O(M \log M)$
   • 动态规划双重循环：$O(M^2)$
   • 总时间复杂度：$O(M^2)$

2. 空间复杂度：

   • 存储线段：$O(M)$
   • dp数组：$O(M)$
   • choices数组：$O(M)$
   • 总空间复杂度：$O(M)$