UVa 531 Compromise

Longest Common Subsequence題型
想法：
    用pre[i][j]來記錄LCS[i][j]是從哪個方向來的，再從pre[N-1][M-1]開始逆向走回並保存答案。

	#include <iostream>
	#include <string>
	#include <vector>
	#include <cstdio>
	using namespace std;
	string A[110], B[110];
	int LCS[110][110] = {0};
	int pre[110][110];
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	while (1) {
	int N = 1, M = 1;
	while (cin >> A[N] && A[N] != "#") ++N;
	while (cin >> B[M] && B[M] != "#") ++M;
	if (N == 1) return 0;
	for (int i = 1; i < N; ++i) {
	for (int j = 1; j < M; ++j) {
	if (A[i] == B[j]) {
	LCS[i][j] = LCS[i-1][j-1] + 1;
	pre[i][j] = 0; // 0 is ↖
	}
	else {
	if (LCS[i-1][j] > LCS[i][j-1]) {
	LCS[i][j] = LCS[i-1][j];
	pre[i][j] = 1; // 1 is ↑
	}
	else {
	LCS[i][j] = LCS[i][j-1];
	pre[i][j] = 2; // 2 is ←
	}
	}
	}
	}
	vector<string *> Ans;
	int i = N - 1, j = M - 1;
	while (i && j) {
	if (pre[i][j] == 0) {
	Ans.push_back(&A[i]);
	--i, --j;
	}
	else if (pre[i][j] == 1)
	--i;
	else
	--j;
	}
	if (!Ans.empty()) {
	cout << **Ans.rbegin();
	for (auto iter = Ans.rbegin() + 1; iter != Ans.rend(); ++iter)
	cout << ' ' << **iter;
	}
	cout << endl;
	}
	}

view raw [UVa] 531 Compromise.cpp hosted with ❤ by GitHub