狄尔沃斯定理求链的划分 – Zechel

狄尔沃斯定理(Dilworth’s theorem)是关于偏序集的极大极小的定理.该定理断言:对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目.

洛谷P1020导弹拦截

当给出一个数列,我们如果要将这个数列从左到右分割取(可以不连续的)子序列,并且要使这个序列是尽可能的长的上升子序列,问可以将原序列分为多少部分。根据狄尔沃斯定理,上述链划分规则得到的链的数目,等于最长反链的长度。上升子序列的反链即为不上升子序列,所以,我们要求的答案就是该序列的最长不上升子序列。

例题类似,不上升序列的反链即最长上升子序列。

另外,值得一提的是,在该题的求解中需要用到nlogn的求上升子序列的方法。在模板中,如果循环里使用upper_bound函数,则求的是最长不下降子序列,如果使用lower_bound函数,最终将得到最长上升子序列,差别即为元素之间是否可相等,代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=100005,INF=0x3f3f3f3f;
int a[N],len;
int b[N];
int pre()
{
    fill(b,b+len,INF);
    for(int i=0;i<len;i++)*upper_bound(b,b+len,a[i])=a[i];
    return lower_bound(b,b+len,INF)-b;
}
int pre2()
{
    fill(b,b+len,INF);
    for(int i=0;i<len;i++)*lower_bound(b,b+len,a[i])=a[i];
    return lower_bound(b,b+len,INF)-b;
}
int main()
{
    len=0;
    while(scanf("%d",&a[len])!=EOF)len++;
    int ans2=pre2();
    reverse(a,a+len);
    int ans1=pre();
    printf("%d\n%d",ans1,ans2);
}

洛谷P1233木棍加工

该题相对抽象,链上的关系相对更加复杂。首先,该题的元素对的顺序是不固定的,为了减少时间消费,我们要先给元素对排序,将L和W大的尽可能放在前面,这样就保证了最优取木料的顺序一定是从前往后。

当Li>=Lj且Wi>=Wj,(i<j),此时这两个元素对满足我们的我们要求的链的关系,那么,它的反链的关系应该定义为:

Li<Lj或者Wi<Wj,(i<j)

所以,我们可以求满足该关系的最长反链,得到的值即是我们要求的答案。由于该题的数据不强,我们用n^2的动态规划法即可完成。

#include <bits/stdc++.h>
using namespace std;
const int N=5005,INF=0x3f3f3f3f;
struct imf
{
    int L,W;
}a[N];
int f[N];
int n;
int pre()
{
    for(int i=0;i<n;i++)
    {
        f[i]=1;
        for(int j=0;j<i;j++)
        {
            if((a[j].L<a[i].L||a[j].W<a[i].W))
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)res=max(res,f[i]);
    return res;
}
int cmp(imf x,imf y)
{
    if(x.L==y.L)return x.W>y.W;
    return x.L>y.L;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d %d",&a[i].L,&a[i].W);
    sort(a,a+n,cmp);
    int len=pre();
    printf("%d\n",len);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

川公网安备 51130202000337号