dirworth定理+双关键字最大上升子序列

显然可以看出是求最小的双关键字不上升子序列的覆盖数。

根据dirworth定理就可以换去求最长的上升子序列。

双关键字的最长上升子序列求法：

先将一个关键字上升地排序，另一个关键字下降，按照原来的那样n^2的做即可。

其实蒟蒻不明白其中的原理，如果有大佬知道的话麻烦告诉一声

代码：

#include
    
     #include
     
      const int maxn = 5005;struct Nodes{    int l, w;    bool operator < (const Nodes &rhs) const    {        return l < rhs.l;    }} s[maxn];int n;int dp[maxn];// 定义最长上升子序列 int main(){    scanf("%d", &n);    for(int i = 1; i <= n; i++)    {        scanf("%d%d", &s[i].l, &s[i].w);    }    std::sort(s + 1, s + n + 1);    for(int i = 1; i <= n; i++)    {        dp[i] = 1;        for(int j = 1; j < i; j++)        {            if(s[i].w < s[j].w && s[i].l > s[j].l)            {                dp[i] = std::max(dp[i], dp[j] + 1);            }        }    }    int ans = -1;    for(int i = 1; i <= n; i++) ans = std::max(ans, dp[i]);    printf("%d\n", ans);    return 0;}