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

题目链接:

http://poj.org/problem?id=1631

题意:

直接看样例，题意是啥？

题解:

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

代码:

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 1e5+10; int a[maxn],ans[maxn]; int main(){ int T = read(); while(T--){ int n = read(); for(int i=1; i<=n; i++) a[i] = read(); memset(ans,0x3f,sizeof(ans)); int mx = -1; for(int i=1; i<=n; i++){ int p = lower_bound(ans+1,ans+1+n,a[i])-ans; ans[p] = a[i]; mx = max(mx,p); } cout << mx << endl; } return 0; }