1 条题解

  • 0
    @ 2025-3-14 14:22:59
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN = 100000;
    int n;
    struct Line
    {
        int l, r, v;
    };
    Line a[MAXN + 5];
    vector<int> temp; // 离散化
    bool cmp(Line a, Line b)
    {
        return a.r < b.r;
    }
    // dp[i]:1~i 这个范围内能得到的最大快乐度
    int dp[MAXN * 2 + 5];
    // s[i] 记录右端点为 i 的所有区间编号
    vector<int> s[MAXN * 2 + 5];
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i].l >> a[i].r >> a[i].v;
    
        // 离散化
        for (int i = 1; i <= n; i++)
        {
            temp.push_back(a[i].l);
            temp.push_back(a[i].r);
        }
        sort(temp.begin(), temp.end());
        for (int i = 1; i <= n; i++)
        {
            // 坐标对应到 1~2n(因为前面没去重,所以中间可能有缺的位置)
            a[i].l = lower_bound(temp.begin(), temp.end(), a[i].l) -
                     temp.begin() + 1;
            a[i].r = lower_bound(temp.begin(), temp.end(), a[i].r) -
                     temp.begin() + 1;
        }
    
        // 把每个区间存入对应右端点中
        sort(a + 1, a + n + 1, cmp);
        for (int i = 1; i <= n; i++)
            s[a[i].r].push_back(i);
    
        // dp
        for (int i = 1; i <= 2 * n; i++)
        {
            dp[i] = dp[i - 1]; // 先继承 1~i-1 的最大快乐值
            // 检查所有右端点在 i 的区间
            // 如果使用了第 j 个区间,那么带来了 a[j].v 的快乐值,然后第 j 个区间范围内就不能用了
            for (int &j : s[i])
                dp[i] = max(dp[i], dp[a[j].l - 1] + a[j].v);
        }
    
        cout << dp[2 * n];
        return 0;
    }
    
    • 1

    信息

    ID
    1794
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    (无)
    递交数
    36
    已通过
    14
    上传者