【算法碎碎念】dilworth定理

迪沃斯定理

对于一个偏序集，最少链划分（划分出集合的个数，并且每一个集合不能再大了，这个时候，个数是最少的）等于最长反链（比如求下降子序列最少划分数，等于最长链的长度）长度。
看例题理解一下。

例题

https://www.luogu.com.cn/problem/solution/P1233

思路

由于想要求最少的，下降子序列划分，所以可以换个思路求，最长上升子序列元素的个数。
最长上升子序列元素的个数=最少划分出的下降子序列的集合个数

粒子：
求2 9 5 1 4序列的最少下降子序列集合的划分：{9，5，4}、{2，1}。总共两个集合。求2 9 5 1 4序列的最长上升序列{1，4}或者{2，9}为2个，所以就是这么一会事情。

AC代码

// VsCode C++模板 | (●'◡'●)
#include 

#include 
using namespace std;
typedef long long LL;
int n, a, b;
struct Object {
    int len, width;
    bool operator()(const Object &a, const Object &b) {
        if (a.len == b.len) {
            return a.width > b.width;
        } else {
            return a.len > b.len;
        }
    }
} objects[5000 + 5];
int dp[5000 + 5], ans = -1;
int main() {
    scanf("%d", &n);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a, &b);
        objects[i].len = a;
        objects[i].width = b;
        dp[i + 1] = 1;
    }
    sort(objects + 0, objects + n, Object());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (objects[i].width > objects[j].width) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(dp[i], ans);
    }
    cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

OlogN的优化

上面的那个for j的循环，不是欲求找一个末尾可以使得，当前i的长度加起来最大嘛。
那我们其实可以使用一下二分做一做。
我们可以缓存一个，当前已经存在的最长上升子序列，就把所有最长的子序列（i之前的）都存起来，并且我们知道这些最长序列的末尾元素知道就好了。
然后把这些已知的最长子序列，从小到达排好，幸运的是，我们可以一边做，一边维护，“从小到大排好”。
我们设置dp[n]的含义是，在i之前，长度为n的子序列，这个序列的末尾元素是多少。（我们力求，dp[n]在最后一个最小，这样不就更好的接入了嘛）
例如
{1，2，5}
{2，3，4}
我们取第二个，也就是{2，3，4}的末尾，dp[3]=4
由于n是有序的，所以可以二分查找一下，就可以了。
代码不给出了，去洛谷看题解吧。
https://www.luogu.com.cn/problem/solution/P1233