# M.J的blog

algorithm,ACM-ICPC

## Dilworth定理及相关题目

即：链的最少划分数=反链的最长长度

POJ 3636:
`#include<iostream>#include<algorithm>#define M 20002using 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;        }        }}`

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