[Codeforces]1399F – Yet Another Segments Subset
本文最后更新于 160 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/cf1399F/

题意

选出若干线段,使其两两不相交,求最多选多少。

解法

先离散化坐标。
设 $f(l,r)$ 为区间 $[l,r]$ 中满足条件的最大选出线段数量。
首先有 $f(l,r) = f(l,r-1)$,然后考虑转移。
对于每个右端点为 $r$ 的线段 $[L,r]$,都有如下转移: $f(l,r) = f(l,L – 1) + f(L,r)$,而对于覆盖整个区间的 $[l,r]$ 线段,如果有则直接加入贡献即可。
一共 $n^2$ 个状态,以 $r$ 为右端点的状态有 $n$ 个,因此每个线段最多被访问 $n$ 次,总复杂度是 $O(n^2)$ 的。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 6e3 + 100;
int T,n;
int H[maxn],cnt;
int L[maxn],R[maxn];
vector<int> V[maxn];
int f[maxn][maxn];
void dfs(int l,int r)
{
    if(f[l][r] != -1) return;
    f[l][r] = 0;
    if(l > r) return;
    dfs(l, r - 1), dfs(l + 1, r);
    f[l][r] = max(f[l][r - 1], f[l + 1][r]);
    int num = 0;
    for(vector<int>::iterator it = V[r].begin();it!=V[r].end();++it)
    {
        int L = *it;
        if (L == l) ++num;
        else if (L - 1 >= l) dfs(l, L - 1), dfs(L, r), f[l][r] = max(f[l][r], f[l][L - 1] + f[L][r]);
    }
    f[l][r] += num;
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) read(L[i]),read(R[i]),H[++cnt] = L[i],H[++cnt] = R[i];
        sort(H + 1,H + 1 + cnt),cnt = unique(H + 1,H + 1 + cnt) - H - 1;
        for(int i = 1;i<=cnt;++i) V[i].clear();
        for (int i = 1; i <= cnt; ++i) for(int j = 1;j<=cnt;++j) f[i][j] = -1;
        for (int i = 1; i <= n; ++i) 
        {
            L[i] = std::lower_bound(H + 1,H + 1 + cnt,L[i]) - H;
            R[i] = std::lower_bound(H + 1,H + 1 + cnt,R[i]) - H;
            V[R[i]].push_back(L[i]);
        }
        dfs(1,cnt);
        printf("%d\n",f[1][cnt]);
    }
    return 0;
}
本文标题:[Codeforces]1399F – Yet Another Segments Subset
本文作者:Clouder
本文链接: https://www.codein.icu/1399f/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇