本文主要是介绍uva 10635 - Prince and Princess(LCS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：10635 - Prince and Princess
题目大意：给出n, m, k，求两个长度分别为m + 1 和 k + 1且由1~n * n组成的序列的最长公共子序列长的。
解题思路：按一般的o(n^2)的算法超时了，所以上网查了下LCS装换成LIS的算法o(nlogn)。算法仅仅是将其中的一个序列重新标号1~m，然后按最长公共子序列的方法去做。
#include <stdio.h>
#include <string.h>
const int N = 90000;int n, m, k, w[N], g[N];int read() {int a;memset(g, 0, sizeof(g));memset(w, 0, sizeof(w));scanf("%d%d%d", &n, &m, &k);for (int i = 0; i <= m; i++) {scanf("%d", &a);w[a] = i + 1;}for (int i = 0; i <= k; i++)scanf("%d", &g[i]);
}int solve() {int dp[N], cnt = 0;memset(dp, 0, sizeof(dp));for (int i = 0; i <= k; i++) {if (!w[g[i]]) continue;int flag = 1;for (int j = 0; j < cnt; j++) {if (w[g[i]] < w[dp[j]]) {dp[j] = g[i];flag = 0;break;}}if (flag) dp[cnt++] = g[i];}return cnt;
}int main() {int cas, t = 1;scanf("%d", &cas);while (cas--) {read();printf("Case %d: %d\n", t++, solve());}return 0;
}
这篇关于uva 10635 - Prince and Princess(LCS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
