POJ 1631 Bridging signals & 2533 Longest Ordered Subsequence

两个都是最长上升子序列，所以就放一起了

1631 因为长度为40000，所以要用O(nlogn)的算法，其实就是另用一个数组c来存储当前最长子序列每一位的最小值，然后二分查找当前值在其中的位置；如果当前点不能作为当前最长子序列的最大值，则更新找到值为两者间的较小值。

2533 就是一个裸的最长上升子序列。。。这里就不多说了，直接dp就好。。。

1611：

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #define maxn 100005

 using namespace std;

 int d;

 int c[maxn];

 int erfen (int d,int n){

     int l=,r=n;

     int mid;mid=(l+r)/;

     while (l<r){

         if (c[mid]<d&&c[mid+]>=d) return mid+;

         if (c[mid]>d)

             r=mid;

         else l=mid+;

         mid=(l+r)/;

     }

     return mid;

 }

 int main (){

     int n;

     int t;

     scanf ("%d",&t);

     while (t--){

         scanf ("%d",&n);

         int ans=;

         memset (c,,sizeof c);

         for (int i=;i<n;i++){

             scanf ("%d",&d);

             int x=erfen (d,ans);//cout<<x;

             if (x>=ans&&c[ans]<d)

                 c[ans++]=d;

             else if (c[x]!=d) c[x]=d;

         }

         printf ("%d\n",ans-);

     }

     return ;

 }

2533：

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #define maxn 1005

 using namespace std;

 int d[maxn],dp[maxn];

 int main (){

     int n;

     while (~scanf ("%d",&n)){

         for (int i=;i<n;i++)

             scanf ("%d",&d[i]);

         int ans=;

         for (int i=;i<n;i++){

             dp[i]=;

             for (int j=;j<i;j++){

                 if (d[j]<d[i])

                     dp[i]=max (dp[i],dp[j]+);

             }

             ans=max (ans,dp[i]);

         }

         printf ("%d\n",ans);

     }

     return ;

 }