poj - 1631 - Bridging signals（LIS）

题意：两列数，每列p(p < 40000)个，两列都按1, 2, 3...排列，初始时左右两列一对一匹配，求这些匹配中不交叉的最大匹配数。

题目链接：http://poj.org/problem?id=1631

——>>求出输入序列的LIS，左边已是升序，所以LIS对应的左边序号也是升序，一一匹配后不会交叉，LIS的长度就是答案。因为p达40000个，O(n^2)的算法不能满足需要，应使用O(nlongn)以下的算法。。

#include <cstdio>
#include <algorithm>
#include <cstring>using std::max;
using std::lower_bound;const int MAXN = 40000 + 10;
const int INF = 0x3f3f3f3f;int P;
int p[MAXN], arrLis[MAXN];
int dp[MAXN];int ReadInt()
{int nRet= 0;char chIn;while ((chIn = getchar()) >= '0' && chIn <= '9'){nRet = nRet * 10 + chIn - '0';}return nRet;
}void Read()
{P = ReadInt();for (int i = 1; i <= P; ++i){p[i] = ReadInt();}
}void Dp()
{int nRet = -1;for(int i = 1; i <= P; i++) arrLis[i] = INF;for(int i = 1; i <= P; i++){int k = lower_bound(arrLis + 1, arrLis + 1 + P, p[i]) - arrLis;arrLis[k] = p[i];nRet = max(nRet, k);}printf("%d\n", nRet);
}int main()
{int n;scanf("%d", &n);getchar();while (n--){Read();Dp();}return 0;
}