挑战练习题2.3动态规划 poj1631 Bridging signals 最长递增子序列

题目链接:

题意:

直接看样例，题意是啥？

题解:

LIS， O(nlogn)的，维护一个数组ans，手动模拟一下就懂了。

代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 #define MS(a) memset(a,0,sizeof(a))
 8 #define MP make_pair
 9 #define PB push_back
10 const int INF = 0x3f3f3f3f;
11 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
12 inline ll read(){
13     ll x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 //////////////////////////////////////////////////////////////////////////
19 const int maxn = 1e5+10;
20 
21 int a[maxn],ans[maxn];
22 
23 int main(){
24     int T = read();
25     while(T--){
26         int n = read();
27         for(int i=1; i<=n; i++)
28             a[i] = read();
29 
30         memset(ans,0x3f,sizeof(ans));
31 
32         int mx = -1;
33         for(int i=1; i<=n; i++){
34             int p = lower_bound(ans+1,ans+1+n,a[i])-ans;
35             ans[p] = a[i];
36             mx = max(mx,p);
37         }
38 
39         cout << mx << endl;
40     }
41 
42     return 0;
43 }