|
|
偏序集的兩個定理：
定理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==-1) break;
a[k++]=j;
while(scanf("%d%d",&i,&j)){
if(i==0&&j==0 ){
LIS();
break;
}
a[k++]=j;
}
}
}
|