例题27 UVa10635 Prince and Princess（DP：LIS的nlogn算法）

本文主要是介绍例题27 UVa10635 Prince and Princess（DP：LIS的nlogn算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

看白书

要点：

这题本来应该是LCS，但因为时间的要求，可以转化为LIS，而且还得用nlogn的算法，基本思路就是用b数组来存储当前b的值在a数组中对应的位置。LIS的nlogn算法的思路就是，每次用g来存储，并每次在其中进行二分查找，注意这里每次更新是不会改变LIS的性质的，最后g的结果不是所需的LIS，这里要注意一下。

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 250 * 250;
int a[maxn],d[maxn];
vector<int> b;int main()
{int t, n, p, q,x;int i, j;scanf("%d", &t);for(int kase=1;kase<=t;kase++){b.clear();memset(a, 0, sizeof(a));scanf("%d%d%d", &n, &p, &q);p++, q++;for (i = 1; i <= p; i++){scanf("%d", &x);a[x] = i;}for (i = 1; i <= q; i++){scanf("%d", &x);if (a[x])b.push_back(a[x]);}int g[maxn];for (i = 1; i < maxn; i++)g[i] = 1000000000;int ans = 0;for (i = 0; i < b.size(); i++)//LIS的nlogn复杂度算法{int k=lower_bound(g + 1, g + b.size(), b[i]) - g;d[i] = k;g[k] = b[i];//每次更新，将较大值换成小值，后面再次二分查找时更加容易找到更大值ans = max(ans, d[i]);}printf("Case %d: %d\n", kase, ans);}return 0;
}

这篇关于例题27 UVa10635 Prince and Princess（DP：LIS的nlogn算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---