ITSA 2084 題目配對

itsa2084.md

ITSA 2084 題目配對

題目

分析

這題是 LIS，不容易想到… 不過測資很弱，用 O(n^2) 的解法即可，而且不用考慮極端的情形（i.e. 沒有任何配對的情況）。另外，題目的 Sample Ouput 的格式是錯的，不需要補零！

AC Code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int LIS(const vector<int>& v) {
	int len = v.size();
	int q[len];
	fill(q, q+len, 1);

	// q[i] = max([q[k] for k in range(i) if v[i] > v[k]]) + 1

	for (int i=0; i<len; i++) {
		for (int k=0; k<i; k++)
			if (v[i] > v[k])
				q[i] = max(q[i], q[k] + 1);
	}

	return *max_element(q, q+len);
}

int main() {
	int N, M;
	cin >> N >> M;

	string A, B;
	cin >> A >> B;

	int index[256];
	memset(index, -1, sizeof(index));
	for (int i=0; i<N; i++)
		index[int(A[i])] = i;

	vector<int> data(M);
	for (int i=0; i<N; i++)
		data[i] = index[int(B[i])];

	// bool any_match = any_of(data.begin(), data.end(), [](const int i) {
	// 	return (i != -1);
	// });
	bool any_match = false;
	for (int i=0; i<M; i++) {
		if (data[i] != -1) {
			any_match = true;
			break;
		}
	}

	if (any_match == false) {
		cout << "0" << endl;
	}
	else {
		int ans = LIS(data);
		cout << ans << endl;
		//cout << setfill('0') << setw(2) << ans << endl;
	}

	return 0;
}