首页 > 代码库 > zoj 1025 - Wooden Sticks
zoj 1025 - Wooden Sticks
题目:求一个序列中最大不上升子序列的个数。
分析:dp,LIS。一个序列中的不上升子序列的最小个数,是他的最大上升子序列长度。
证明:首先求串的最大上升子序列,那么每个元素一定属于一个不同的不下降串;
如果,取第一个最大上升子序列,那么每个元素一定是集合中的最大值;
这些最大值可以分别确定一个不上子串,对应一个集合,所以下界是|LIS|;
然后,假设存在一个集合P,最大值p不在lis中,他不属于上面的集合;
他自己确定一个不上升序列,设他前面的集合的最大值为lis(i);
则有lis(i)>= p(否则p就是lis(i+1));用p替换掉lis(i)所在集合中,
比p小的部分,我们得到新的lis(i)确定的集合和一个新的独立集合P1;
设P1最大值为p1,这时有两种可能:
1. lis(i-1)< p1 < lis(i)可构成更长的lis,那么结果还是|LIS|,得证;
2. lis(i-1)>= p1重复上述操作,不断得到Pj集合,直到1成立或者i = 1;
如果i为1,则pj < lis(1),去顶更长的lis,否则1成立,得证。
说明:利用单调队列可以是O(N^2)的算法,优化成O(NlogN)。(2011-09-19 01:43)
#include <stdio.h> #include <stdlib.h> typedef struct node { int l,w; }stick; int BS( int h, int key, int *MUQ ) { int l = 0,m; while ( l < h ) { m = (l+h)/2; if ( key >= MUQ[ m ] ) h = m; else l = m+1; } return h; } int cmp( const void* a, const void* b ) { stick *p = (stick *)a; stick *q = (stick *)b; if ( p->l == q->l ) return p->w - q->w; return p->l - q->l; } int main() { stick Stick[ 5001 ]; int MUQ[ 5001 ]; int t,n,i,tail,j; while ( scanf("%d",&t) != EOF ) while ( t -- ) { scanf("%d",&n); for ( i = 1 ; i <= n ; ++ i ) scanf("%d%d",&Stick[ i ].l,&Stick[ i ].w); qsort( &Stick[ 1 ], n, sizeof( stick ), cmp ); tail = 0; MUQ[ 0 ] = Stick[ 1 ].w; for ( i = 2 ; i <= n ; ++ i ) if ( Stick[ i ].w < MUQ[ tail ] ) MUQ[ ++ tail ] = Stick[ i ].w; else MUQ[ BS( tail, Stick[ i ].w, MUQ ) ] = Stick[ i ].w; printf("%d\n",tail+1); } return 0; }
zoj 1025 - Wooden Sticks