题意:两列数,每列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; }