DP——最长上升子序列（n^2与n log n）

作为NOIP中的知名的问题，最长不下降子序列可谓是灰常重要……

废话不多说，正题：
最长不下降有两种方法，然而都是DP……

裸DP，时间复杂度O（n^2）：

定义：dp[ i ]=以a[ i ]为结尾的最长上升子序列的长度，so，dp[ i ]=max(1,dp[ j ]+1 | j < i且a[ j ] < a[ i ] )；

代码：

 1 int n;
 2 int a[10000];
 3 int dp[10000];
 4 
 5 void solve(){
 6   int res=0;
 7   for(int i=1;i<=n;i++){
 8     dp[i]=1;
 9     for(int j=1;j<i;j++)  if( a[ j ]<a[ i ] ){
10       dp[i]=max(dp[i],dp[j]+1);
11     }
12     res=max(res,dp[i]);
13   } 
14   cout<<res<<endl;
15 }

但…………此代码是我从书上抄的，因为…………我也不会…………我也不想学………………因为我会O（n log n）的……orz；

下面介绍O（n log n）的：

dp[1]=a[1];

从2————n for循环

我们定义dp[i]为长度为i的最长上升子序列的最后一个数的最小值，由此可推得dp是不下降的，每当我们发现了一个数比dp[len]大，就len++,dp[len]=这个数，否则，在dp中寻找一个dp[j-1]<这个数<dp[j] ，使dp[j]=min(dp[j],这个数)，以此来维护正确性。又因dp是不下降的因此可以用二分求j。

代码：

1 int dp[1000]
2 void solve(){
3   fill(dp+1,dp+n+1,INF);
4   for(int i=1;i<=n;i++){
5     *lower_bound(dp+1,dp+1+n,a[i])=a[i];
6   }
7   printf("%d",lower_bound(dp+1,dp+1+n,INF)-dp);
8 }

好吧，以上这个也是我抄的，但貌似不太靠谱，下一个是我的，反正比上面的靠谱点儿……

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<string>
 6 #include<cmath>
 7 using namespace std;
 8 int d[2000000],a[2000000],n,len,l,r,mid;
 9  
10 int main(){
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
13     d[1]=a[1];
14     len=1;
15     for (int i=2;i<=n;i++){
16         if(a[i]>d[len]){
17             len++;
18             d[len]=a[i];
19         }else{
20             l=1;r=len-1;
21             while(l<=r){
22                 mid=(l+r)/2;
23                 if(d[mid]>=a[i]) r=mid-1;
24                 else l=mid+1;
25             }
26             d[l]=min(a[i],d[l]);
27         }
28     }
29     printf("%d",len);
30     return 0;
31 }

上面的也不靠谱……

1 d[1]=a[1]; 
2 int len=1;
3 for (int i=2;i<=n;i++){
4       if (a[i]>d[len]) d[++len]=a[i]; 
5       else{
6              int j=upper_bound(d+1,d+len+1,a[i])-d;
7              d[j]=a[i]; 
8        }
9 }