UVa 111 History Sorting

題意：
    Luckycat中文翻譯。
想法：
    這題有個陷阱，以Sample input舉例：
10
3 1 2 4 9 5 10 6 8 7
4 7 2 3 10 6 9 1 5 8

由這行來看：3 1 2 4 9 5 10 6 8 7
"事件1在位置3"，"事件2在位置1"，"事件3在位置2"......"事件10在位置7"。

因此事件真正的排序是
10
2 3 1 4 6 8 10 9 5 7
8 3 4 1 9 6 2 10 7 5
然後再用LCS找出最大的長度。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N, pos, Ans[30], num[30], LCS[30][30] = {0};
	int main()
	{
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
	scanf("%d", &pos);
	Ans[pos] = i;
	}
	while (scanf("%d", &pos) != EOF) {
	num[pos] = 1;
	for (int i = 2; i <= N; ++i) {
	scanf("%d", &pos);
	num[pos] = i;
	}
	int Max = 0;
	for (int i = 1; i <= N; ++i) {
	for (int j = 1; j <= N; ++j) {
	if (Ans[i] == num[j])
	LCS[i][j] = LCS[i-1][j-1] + 1;
	else
	LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
	if (LCS[i][j] > Max) Max = LCS[i][j];
	}
	}
	printf("%d\n", Max);
	}
	}

view raw [UVa] 111 History Sorting.cpp hosted with ❤ by GitHub