题目链接：

题目

Greatest Common Increasing Subsequence

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

问题描述

This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.

输入

Each sequence is described with M - its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.

输出

output print L - the length of the greatest common increasing subsequence of both sequences.

样例

input

1

5

1 4 2 5 -12

4

-12 1 2 4

output

2

题意

求两个串的最长公共上升子序列（LCIS）

题解

dp[j]表示第一个串的前i个和第二个串的前j个的以b[j]结尾的公共最长上升子序列的长度。

代码

O(n^3):

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = 555;

int dp[maxn];

int a[maxn], b[maxn];

int n, m;

void init() {

	memset(dp, 0, sizeof(dp));

}

int main() {

	int tc;

	scanf("%d", &tc);

	while (tc--) {

		init();

		scanf("%d", &n);

		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

		scanf("%d", &m);

		for (int i = 1; i <= m; i++) scanf("%d", &b[i]);

		int ans = 0;

		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= m; j++) {

				if (a[i] == b[j]) {

					dp[j] = 1;//b[0]是非法的！

					for (int k = 0; k < j; k++) {

						if (b[k] < b[j] && dp[j] < dp[k] + 1) {

							dp[j] = dp[k] + 1;

						}

					}

				}

				ans = max(ans, dp[j]);

			}

		}

		printf("%d\n", ans);

		if (tc) printf("\n");

	}

	return 0;

}

O(n^2):k循环其实可以不用，用Max一边扫j，一边记录就可以了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn = 555;

int dp[maxn];

int a[maxn], b[maxn];

int n, m;

void init() {

	memset(dp, 0, sizeof(dp));

}

int main() {

	int tc;

	scanf("%d", &tc);

	while (tc--) {

		init();

		scanf("%d", &n);

		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

		scanf("%d", &m);

		for (int i = 1; i <= m; i++) scanf("%d", &b[i]);

		int ans = 0;

		for (int i = 1; i <= n; i++) {

			int Max = 0;

			for (int j = 1; j <= m; j++) {

				if (b[j]<a[i]&&Max<dp[j]) {

					Max = dp[j];

				}

				else if (a[i] == b[j]) {

					dp[j] = Max + 1;

				}

				ans = max(ans, dp[j]);

			}

		}

		printf("%d\n", ans);

		if (tc) printf("\n");

	}

	return 0;

}