nyoj236 偏序集+dilworth定理的应用

题目大意：中文题。

算法思路：这道题可以通过dilworth定理，将原序列排序后，转化为求有多少个单调递增子序列（即求最大递减子序列的长度）。但是当我直接求单调递增子序列的个数的时候就过了，但转化为求最大递减子序列的长度的时候就超时了= =，实在是莫名其妙。。还是请各位大神帮我看看。。。

 

先看一下什么是偏序集，以及dilworth定理（以下内容转载自http://blog.csdn.net/sd6264456/article/details/8647752）：

在Partially order set(偏序集)有一个非常NX的定理叫DilworthTheorem。上图是偏序集的一个Hasse diagram，偏序集的定义是

偏序是在集合X上的二元关系≤，它满足自反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:
自反性：a≤a;
反对称性：如果a≤b且b≤a，则有a=b;
传递性：如果a≤b且b≤c，则a≤c 。

带有偏序关系的集合称为偏序集。
令(X,≤)是一个偏序集，对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比。
在X中，对于元素a，如果任意元素b，由b≤a得出b=a，则称a为极小元。

一个反链A是X的一个子集，它的任意两个元素都不能进行比较。
一个链C是X的一个子集，它的任意两个元素都可比。

下面是两个重要定理：
定理1令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

搞清楚了反链和链的定义，就能够很好的从HasseDiagram中得到理解。链就是从纵向的角度看 Hasse Diagram ,反链是从横向的角度看HasseDiagram。

定理一，就是至少有r行构成反链关系。

定理二，就是至少有m列构成链关系。

  我们来考虑一个导弹拦截问题，就是求一个序列的最长不上升子序列，以及求能最少划分成几组不上升子序列。很显然第一个是动态规划，动态规划的过程就是求HasseDiagram的过程！！！

  第二问就是求最少能够划分成几个链，根据定理2，很显然就是反链的最大长度。反链就是一个上升子序列。即求一个严格上升子序列的最大长度。

  注意一个问题是，在获得偏序集有几个主链的时候，需要对数据集先进行排序，然后从头开始，沿着主链顺序DFS。由于导弹拦截的问题，天然有序，形成了严格上升自序列，所以没有凸显这个问题！

 

 

 

 

先上个ac的代码(直接求个数的)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 5050
int t,n;
typedef struct Node
{
    int l,w;
};
Node nodes[MAXN];
int dp[MAXN],MAXX;
bool cmp(Node n1,Node n2)
{
    if(n1.l!=n2.l)
        return n1.l<n2.l;
    return n1.w<n2.w;
}
int main()
{

    scanf("%d",&t);

    while(t--)
    {

        scanf("%d",&n);

        int ans=0;

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&nodes[i].l,&nodes[i].w);
        }




        sort(nodes+1,nodes+n+1,cmp);


        for(int i=1;i<=n;i++)
        {

            if(dp[i]==0)
            {
                ans++;
                int m=nodes[i].w;
                for(int j=i+1;j<=n;j++)
                {

                    if(nodes[j].w>=m&&dp[j]==0)
                    {
                        m=nodes[j].w;
                        dp[j]=1;
                    }

                }

            }
        }


        printf("%d\n",ans);

    }


    return 0;
}

 接下来是超时的(转化为求最大递减子序列的长度的)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 5050
int t,n;
typedef struct Node
{
    int l,w;
};
Node nodes[MAXN];
int dp[MAXN],MAXX;
bool cmp(Node n1,Node n2)
{
    if(n1.l!=n2.l)
        return n1.l<n2.l;
    return n1.w<n2.w;
}
int main()
{

    scanf("%d",&t);

    while(t--)
    {

        scanf("%d",&n);

        int ans=0;

        for(int i=1;i<=n;i++)
        {
            dp[i]=1;
        }

        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&nodes[i].l,&nodes[i].w);
        }




        sort(nodes+1,nodes+n+1,cmp);


        for(int i=n-1;i>=1;i--)
        {

            for(int j=i+1;j<=n;j++)
            {
                if(nodes[i].w>nodes[j].w)
                {
                    if(dp[i]<dp[j]+1)
                        dp[i]=dp[j]+1;
                }
            }

        }

        int MAXX=0;
        for(int i=1;i<=n;i++)
        {
            if(MAXX<dp[i])
                MAXX=dp[i];
        }

        printf("%d\n",MAXX);

    }


    return 0;
}