Longest Increasing Subsequence(LIS) 一个美丽的名字
非常经典的线性结构dp
[朴素]：O(n^2)
d(i)=max{0,d(j) :j<i&&a[j]<a[i]}+1
直接两个for
[二分查找优化]：O(n^2)
g(i):d值为i的最小的a 每次更新然后lower_bound即可 ［大于等于］
lower_bound
Return iterator to lower bound
Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.
The elements are compared using operator< for the first version, and comp for the second. The elements in the range shall already be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.
[线段树优化]：同上－－－－－实质：二维偏序问题
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
[例题]比如 NOIP2004合唱队形
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
正着一遍LIS，反着一遍LIS
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int N=105,INF=1e6; 7 inline int read(){ 8 int x=0,f=1; 9 char ch=getchar(); 10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} 11 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} 12 return x; 13 } 14 15 int n,d[N],g[N],a[N],f[N],ans=0; 16 17 void dp(){ 18 for(int i=1;i<=n;i++) g[i]=INF; 19 for(int i=1;i<=n;i++){ 20 int k=lower_bound(g+1,g+1+n,a[i])-g;//printf("%d d\n",k); 21 d[i]=k; 22 g[k]=a[i]; 23 } 24 reverse(a+1,a+n+1); 25 for(int i=1;i<=n;i++) g[i]=INF; 26 for(int i=1;i<=n;i++){ 27 int k=lower_bound(g+1,g+1+n,a[i])-g;//printf("%d f\n",k); 28 f[i]=k; 29 g[k]=a[i]; 30 } 31 32 33 } 34 int main() { 35 n=read(); 36 for(int i=1;i<=n;i++) a[i]=read(); 37 38 dp(); 39 for(int i=1;i<=n;i++) ans=max(ans,f[n-i+1]+d[i]-1); 40 printf("%d",n-ans); 41 return 0; 42 }
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
Longest Decreasing Subsequence(LDS) （不知道有没有这个名字）
也可以用二分，改一改，保留a最大的，找第一个小于等于的
1 bool cmp(int a,int b){ 2 return a>b; 3 } 4 void lds(){ 5 for(int i=1;i<=n;i++){ 6 int k=lower_bound(g+1,g+1+n,a[i],cmp)-g;//printf("%d f\n",k); 7 f[i]=k; 8 g[k]=a[i]; 9 } 10 }
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
不上升，不下降
用upper_bound，找第一个大于的
［例题］
Longest Increasing Subsequence
原文：http://www.cnblogs.com/candy99/p/5738927.html