题解：CF1399F Yet Another Segments Subset

__FL__ · 2025-08-14 16:43:18 · 题解

Solution

考虑如果不能选有包含关系的线段时应该怎么做。显然有 dp 转移：

线段按右端点排序后可以二维数点做到 O(n\log n)。

回到正题。观察式子，发现一个贪心的性质，如果某条线段包含了一些其他的线段，显然在这些小线段不冲突的情况下，大线段应该“携带”尽量多的小线段参与转移。因此我们可以给每个线段赋一个权值，其意义为它能容纳的最多小线段数量（包括自己），求权值的过程可以视作一个个子问题，对其所有能容纳的小线段跑一遍 dp，求得大线段的权值。

细节上，求权值前要以线段长度进行排序，不然会混。细节可参考代码。

由于每一条线段都要分别 dp，所以复杂度是 O(n^2\log n)。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3005;
int t,n,dp[N],f[N<<3];
vector<int>vec;
struct seg
{
    int l,r,w,p;
}a[N],b[N];
bool cmp1(seg a,seg b)
{
    return a.r-a.l < b.r-b.l;
}
bool cmp(seg a,seg b)
{
    return a.r == b.r? a.l < b.l: a.r < b.r;
}
void update(int root,int l,int r,int x,int num)
{
    if (l >= r)
    {
        f[root] = max(f[root],num);
        return;
    }
    int mid = (l+r)/2;
    if (x <= mid) update(root*2,l,mid,x,num);
    else update(root*2+1,mid+1,r,x,num);
    f[root] = max(f[root*2],f[root*2+1]);
}
int query(int root,int l,int r,int ql,int qr)
{
    if (ql > qr) return 0;
    if (ql <= l && qr >= r) return f[root];
    int mid = (l+r)/2;
    if (qr <= mid) return query(root*2,l,mid,ql,qr);
    if (ql > mid) return query(root*2+1,mid+1,r,ql,qr);
    return max(query(root*2,l,mid,ql,mid),query(root*2+1,mid+1,r,mid+1,qr));
}
signed main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n;
        vec.clear();
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].l >> a[i].r;
            a[i].w = 1,a[i].p = i;
            vec.push_back(a[i].l),vec.push_back(a[i].r);
        }
        sort(vec.begin(),vec.end());
        vec.erase(unique(vec.begin(),vec.end()),vec.end());
        for (int i = 1; i <= n; i++)
            a[i].l = lower_bound(vec.begin(),vec.end(),a[i].l)-vec.begin()+1,
            a[i].r = lower_bound(vec.begin(),vec.end(),a[i].r)-vec.begin()+1;
        sort(a+1,a+n+1,cmp1);
        for (int i = 1; i <= n; i++)
        {
            memset(f,0,sizeof f);
            int cnt = 0;
            for (int j = 1; j <= n; j++)
                if (i != j && a[j].l >= a[i].l && a[j].r <= a[i].r) b[++cnt] = a[j];
            sort(b+1,b+cnt+1,cmp);
            int mx = 0;
            for (int j = 1; j <= cnt; j++)
                dp[j] = query(1,1,n<<1,1,b[j].l-1)+b[j].w,mx = max(mx,dp[j]),update(1,1,n<<1,b[j].r,dp[j]);
            a[i].w = mx+1;
        }
        memset(f,0,sizeof f);
        sort(a+1,a+n+1,cmp);
        int mx = 0;
        for (int j = 1; j <= n; j++)
            dp[j] = query(1,1,n<<1,1,a[j].l-1)+a[j].w,mx = max(mx,dp[j]),update(1,1,n<<1,a[j].r,dp[j]);
        cout << mx << '\n';
    }
    return 0;
}