1045.md

1045

• 1046 Shortest Distance (20 point(s))
• LIS / LCS

LIS

#include <iostream>
#include <algorithm>
using namespace std;

// input
int N;	// 0 < N <= 200
int M;	// 0 < M <= 200
const int MAX_M = 200 + 5;
int hash_table[MAX_M];
// 5 2 3 1 5 6 
// 0 1 2 3 4 5 
int L;	// 0 < L <= 1e4
const int MAX_L = 1e4 + 5;
int colors[MAX_L];
int num = 0;
// solve
int dp[MAX_L];
// output
int res = 0; // 0 <= res <= L

int main() {
	// input
	cin >> N;
	cin >> M;
	for (int i = 0; i < MAX_M; i++) {
		hash_table[i] = -1;
	}
	for (int m = 0; m < M; m++) {
		int x;
		cin >> x;
		hash_table[x] = m;
	}
	cin >> L;
	for (int l = 0; l < L; l++) {
		int x;
		cin >> x;
		if (hash_table[x] >= 0) {
			colors[num++] = hash_table[x];
		}
	}
	// solve
	for (int i = 0; i < num; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (colors[j] <= colors[i] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
		}
		res = max(res, dp[i]);
	}
	// output
	cout << res << endl;
	return 0;
}

/*
Sample Input:
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
Sample Output:
7
*/

LCS

#include <iostream>
#include <algorithm>
using namespace std;

// input
int N;	// 0 < N <= 200
int M;	// 0 < M <= 200
const int MAX_M = 200 + 5;
int favorite[MAX_M];
int L;	// 0 < L <= 1e4
const int MAX_L = 1e4 + 5;
int colors[MAX_L];
// solve
int dp[MAX_M][MAX_L];
// output

int main() {
	// input
	cin >> N;
	cin >> M;
	for (int m = 1; m <= M; m++) {
		cin >> favorite[m];
	}
	cin >> L;
	for (int l = 1; l <= L; l++) {
		cin >> colors[l];
	}
	// solve
	// boundary
	for (int i = 0; i <= M; i++) {
		dp[i][0] = 0;
	}
	for (int j = 0; j <= L; j++) {
		dp[0][j] = 0;
	}
	// state transition equation
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= L; j++) {
			int Max = max(dp[i - 1][j], dp[i][j - 1]);
			if (favorite[i] == colors[j]) {
				dp[i][j] = Max + 1;
			}
			else {
				dp[i][j] = Max;
			}
		}
	}
	// output
	cout << dp[M][L] << endl;
	return 0;
}

/*
Sample Input:
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
Sample Output:
7
*/

References

• 算法笔记
• 【PAT 1045】 Favorite Color Stripe 最长公共子序列LCS