首页 > 代码库 > pat l2-14 列车调度 dilworth+nlog(n)最长上升子序列

pat l2-14 列车调度 dilworth+nlog(n)最长上升子序列

关于dilworth定理 这里引用一个大神的(http://blog.csdn.net/xuzengqiang/article/details/7266034)

偏序的概念:

设A是一个非空集,P是A上的一个关系,若关系P是自反的、反对称的、和传递的,则称P是集合A上的偏序关系。
即P适合下列条件:
(1)对任意的a∈A,(a,a)∈P;
(2)若(a,b)∈P且(b,a)∈P,则a=b;
(3)若(a,b)∈P,(b,c)∈P,则(a,c)∈P,则称P是A上的一个偏序关系。带偏序关系的集合A称为偏序集或半序集。
若P是A上的一个偏序关系,我们用a≤b来表示(a,b)∈P。

比方说:(A,≤)是偏序集,A={1,2,3},偏序≤在A上的大于等于关系。则有:≤={<3,3>,<3,2>,<3,1>,<2,2>,<2,1>,<1,1>},则有3≤2,2≤2,2≤1....
举如下例子说明偏序关系:
1、实数集上的小于等于关系是一个偏序关系。
2、设S是集合,P(S)是S的所有子集构成的集合,定义P(S)中两个元素A≤B当且仅当A是B的子集,即A包含于B,则P(S)在这个关系下成为偏序集。
3、设N是正整数集,定义m≤n当且仅当m能整除n,不难验证这是一个偏序关系。注意它不同于N上的自然序关系。

 在Partially order set(偏序集)有一个非常NX的定理叫Dilworth Theorem。偏序集的定义是

偏序是在集合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不可比。

例:(A,≤)是偏序集,其中A={1,2,3,4,5},其中≤是整除关系,那么对任意的x∈p都有1≤x,所以1和1,2,3,4,5都是可比的,但是2不能整除3,且3不能整除2,所以2和3是不可比的。
       在X中,对于元素a,如果任意元素b,由b≤a得出b=a,则称a为极小元。

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

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

证明:设p为最少反链个数
      (1)先证明X不能划分成小于r个反链。由于r是最大链C的大小,C中任两个元素都可比,因此C中任两个元素都不能属于同一反链。所以p>=r。
      (2)设X1=X,A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2,必存在X1中的元素a1,使得a1<=a2。令A2是X2中极小元的集合,从X2中删除A2得到X3……最终,会有一个Xk非空而X(k+1)为空。于是A1,A2,...,Ak就是X的反链的划分,同时存在链a1<=a2<=...<=ak,其中ai在Ai内。由于r是最长链大小,因此r>=k。由于X被划分成了k个反链,因此r>=k>=p。因此r=p,定理1得证。

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

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

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

题目总结:hdu 3335,poj 1065,1548,3636,nyist 255

题目链接:poj 2065http://poj.org/problem?id=1065

关键是理解链和反链的概念 链(反链)的最大长度等于反链(链)的最小划分数 
这道题目的链的关系是递减(合理调度) 想求最小的链的划分数 求最长的反链(上升子序列)的长度就可以了
Dilworth 到这里为止 下面讲下 nlogn优化的上升子序列
这里定义一个t[i]表示长度为i的上升序列的末尾元素 d[i]表示t[i] 所有可取值中的最小值 a[i]存储值
那么 在遍历的时候 当(a[i] > t[len]) 那么LIS就可以扩展;否则我们找个合适的位置更新t[]的值(这里有点贪心的感觉)
下面是大佬的具体优化过程

设 A[t]表示序列中的第t个数,F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度,初始时设F [t] = 0(t = 1, 2, ..., len(A))。则有动态规划方程:F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。 

现在,我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y],满足 
(1)x < y < t 
(2)A[x] < A[y] < A[t] 
(3)F[x] = F[y] 

 

此时,选择F[x]和选择F[y]都可以得到同样的F[t]值,那么,在最长上升子序列的这个位置中,应该选择A[x]还是应该选择A[y]呢? 

 

很明显,选择A[x]比选择A[y]要好。因为由于条件(2),在A[x+1] ... A[t-1]这一段中,如果存在A[z],A[x] < A[z] < a[y],则与选择A[y]相比,将会得到更长的上升子序列。 
再根据条件(3),我们会得到一个启示:根据F[]的值进行分类。对于F[]的每一个取值k,我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值,即D[k] = min{A[t]} (F[t] = k)。 

注意到D[]的两个特点: 
(1) D[k]的值是在整个计算过程中是单调不下降的。 
(2) D[]的值是有序的,即D[1] < D[2] < D[3] < ... < D[n]。 

利 用D[],我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A [t] > D[len],则将A[t]接在D[len]后将得到一个更长的上升子序列,len = len + 1, D[len] = A [t];否则,在D[1]..D[len]中,找到最大的j,满足D[j] < A[t]。令k = j + 1,则有A [t] <= D[k],将A[t]接在D[j]后将得到一个更长的上升子序列,更新D[k] = A[t]。最后,len即为所要求的最长上 升子序列的长度。 (http://blog.csdn.net/dangwenliang/article/details/5728363/)



代码倒是短小精悍 妈蛋。
#include<iostream> #include<algorithm> #include<cstring> #define inf 1000009 using namespace std; int main() { int n; cin>>n; int d[100001],a[100001]; for(int i=0;i<n;i++) cin>>a[i]; int len=1; d[0]=-1; d[1]=a[0]; for(int i=1;i<n;i++) { if(a[i] > d[len]) d[++len]=a[i];//拼接上一个 else { int pos=lower_bound(d,d+len,a[i])-d;//在【0,len-1】找到第一个比a[i]大的pos // cout<<pos<<endl; d[pos]=a[i]; } } cout<<len<<endl; return 0; }

pat l2-14 列车调度 dilworth+nlog(n)最长上升子序列