首页 > 代码库 > POJ 1631 Bridging signals & 2533 Longest Ordered Subsequence

POJ 1631 Bridging signals & 2533 Longest Ordered Subsequence

2024-07-14 21:46:18   220人阅读

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

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\n",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\n",ans);25     }26     return 0;27 }

 


联系
我们