网站编辑外包,软文有哪些发布平台,网站设计制作哪里好,公司网站建设费用 知乎http://blog.csdn.net/acdreamers/article/details/7626671 学习一下Dilworth定理 推荐一篇写得很好博客 要求最少的覆盖#xff0c;按照Dilworth定理 最少链划分 最长反链长度 所以最少系统 最长导弹高度上升序列长度。 之前写的LIS模板不对。。。。。。 1 #includecst…http://blog.csdn.net/acdreamers/article/details/7626671 学习一下Dilworth定理 推荐一篇写得很好博客 要求最少的覆盖按照Dilworth定理 最少链划分 最长反链长度 所以最少系统 最长导弹高度上升序列长度。 之前写的LIS模板不对。。。。。。 1 #includecstdio2 #includecstring3 #includeiostream4 #includequeue5 #includestack6 #includecmath7 #includealgorithm8 using namespace std;9 #define clc(a,b) memset(a,b,sizeof(a))10 #define inf 0x3f3f3f3f11 const int N10010;12 #define LL long long13 const double eps 1e-5;14 const double pi acos(-1);15 // inline int r(){16 // int x0,f1;char chgetchar();17 // while(ch9||ch0){if(ch-) f-1;chgetchar();}18 // while(ch0ch9){xx*10ch-0;chgetchar();}19 // return x*f;20 // }21 const int maxn 500010;22 int a[maxn];23 24 struct Node{25 int x,y;26 };27 Node A[N];28 int d[N];29 30 bool cmp(Node a,Node b){31 return a.xb.x||(a.xb.xa.yb.y);32 }33 34 // int Search(int num,int low,int high){35 // int mid;36 // while(lowhigh){37 // mid(lowhigh)/2;38 // if(numb[mid]) lowmid1;39 // else highmid-1;40 // }41 // return low;42 // }43 44 // int DP(int n){45 // int len,pos;46 // b[1]a[1];47 // len1;48 // for(int i2;in;i){49 // if(a[i]b[len]){50 // b[len]a[i];51 // }52 // else {53 // posSearch(a[i],1,len);54 // b[pos]a[i];55 // }56 // }57 // return len;58 // }59 60 int BSearch(int l,int r,int x) 61 { 62 while(l r) 63 { 64 int m (l r) 1; 65 if(x d[m]) r m; 66 else l m 1; 67 } 68 return l; 69 } 70 71 int DP(int a[],int n) 72 { 73 d[0] -1; 74 int len 1; 75 for(int i1;in;i) 76 { 77 d[len] inf; 78 int j BSearch(0,len,a[i]); 79 if(j len) len; 80 d[j] a[i]; 81 } 82 return len - 1; 83 } 84 int main(){85 int n,T;86 scanf(%d,T);87 while(T--){88 scanf(%d,n);89 for(int i1;in;i)90 scanf(%d%d,A[i].x,A[i].y);91 sort(A1,An1,cmp);92 // for(int i1;in;i){93 // printf(x:%d y:%d\n,A[i].x,A[i].y);94 // }95 for(int i1;in;i)96 a[n-i1]A[i].y;97 // for(int i1;in;i)98 // printf(x:%d ,a[i]);99 printf(%d\n,DP(a,n));
100 }
101 return 0;
102 } View Code 转载于:https://www.cnblogs.com/ITUPC/p/5406126.html
