POJ 1631 Bridging signals & 2533 Longest Ordered Subsequence

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

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

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

1611：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #define maxn 100005
 6 using namespace std;
 7 
 8 int d;
 9 int c[maxn];
10 
11 int erfen (int d,int n){
12     int l=0,r=n;
13     int mid;mid=(l+r)/2;
14     while (l<r){
15         if (c[mid]<d&&c[mid+1]>=d) return mid+1;
16         if (c[mid]>d)
17             r=mid;
18         else l=mid+1;
19         mid=(l+r)/2;
20     }
21     return mid;
22 }
23 
24 int main (){
25     int n;
26     int t;
27     scanf ("%d",&t);
28     while (t--){
29         scanf ("%d",&n);
30         int ans=1;
31         memset (c,0,sizeof c);
32         for (int i=0;i<n;i++){
33             scanf ("%d",&d);
34             int x=erfen (d,ans);//cout<<x;
35             if (x>=ans&&c[ans]<d)
36                 c[ans++]=d;
37             else if (c[x]!=d) c[x]=d;
38         }
39         printf ("%d
",ans-1);
40     }
41     return 0;
42 }

2533：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #define maxn 1005
 6 using namespace std;
 7 
 8 int d[maxn],dp[maxn];
 9 
10 int main (){
11     int n;
12     while (~scanf ("%d",&n)){
13         for (int i=0;i<n;i++)
14             scanf ("%d",&d[i]);
15         int ans=0;
16         for (int i=0;i<n;i++){
17             dp[i]=1;
18             for (int j=0;j<i;j++){
19                 if (d[j]<d[i])
20                     dp[i]=max (dp[i],dp[j]+1);
21             }
22             ans=max (ans,dp[i]);
23         }
24         printf ("%d
",ans);
25     }
26     return 0;
27 }

POJ 1631 Bridging signals & 2533 Longest Ordered Subsequence

相关推荐