M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

Dilworth定理及相关题目

偏序集的两个定理:
定理1) 令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理:
定理2) 令(X,≤)是一个有限偏序集,并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
 即:链的最少划分数=反链的最长长度
相关的题目有pku 1065,pku 3636,pku 1548
POJ 3636:
#include<iostream>
#include
<algorithm>
#define M 20002
using namespace std;
struct Node{
    
int h,w;
}
a[M];
int tail[M],n;
void LIS(int n){
    
int i,j,m,len,mid,low,high;
    len
=1;tail[1]=a[1].h;
    
for(i=2;i<=n;i++){
        
if(tail[len]<=a[i].h) {
            len
++;
            tail[len]
=a[i].h;
        }

        
else{
            low
=1;high=len; 
            
while(low<high){
                mid
=(low+high)/2;
                
if(a[i].h>=tail[mid]) low=mid+1;
                
else high=mid;
            }

            tail[low]
=a[i].h;
        }

    }
                    
    printf(
"%d\n",len);      
}

bool cmp(Node a,Node b){
    
if(a.w!=b.w)return a.w>b.w;
    
else return a.h<b.h;
}

int main()
{
    
int i,j,k,cas;
    scanf(
"%d",&cas);    
    
while(cas--){
        scanf(
"%d",&n);
        
for(i=1;i<=n;i++)
            scanf(
"%d%d",&a[i].w,&a[i].h);
        sort(a
+1,a+1+n,cmp);
        LIS(n);
    }

    
//system("pause");
    return 0;
}
POJ  1548:
#include<iostream>
#include
<algorithm>
using namespace std;
int k,a[700],tail[800],b[860];
void LIS(){
    
int i,j,m,n,len,mid,left,right;
    n
=1;
    
for(i=k-1;i>=1;i--) b[n++]=a[i];
    n
--;
    len
=1;tail[1]=b[1];
    
for(i=2;i<=n;++i){
        
if(b[i]>tail[len]){
            len
++;
            tail[len]
=b[i];
        }

        
else{
            left
=1;right=len;
            
while(left<right){              //二分查找插入的位置 
                mid=(left+right)/2;
                
if(tail[mid]<b[i]) left=mid+1;
                    
else  right=mid;
                }

            tail[left]
=b[i];                //插入 
        }
 
    }
                    
    printf(
"%d\n",len);      
}

int main()
{
    
int i,j,m,n;
    
while(1){
        k
=1;
        scanf(
"%d%d",&i,&j);
        
if(i==-1&&j==-1break;
        a[k
++]=j;
        
while(scanf("%d%d",&i,&j)){
            
if(i==0&&j==0 ){
                LIS();
                
break;        
            }

            a[k
++]=j;
        }
    
    }

}

posted on 2010-05-28 18:35 M.J 阅读(713) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理