1045. Favorite Color Stripe (30)

    最長公共非連續子序列的變種

#include <iostream>
#include <cstdio>

using namespace std;

int favorite[205] = {0};
int stripe[10005] = {0};
int matrix[10005][205] = {0};

int n, m, l;

int lcs(){
	for(int i = 1; i <= l; ++i){
        for(int j = 1; j <= m; ++j){
            int maxlen = max(max(matrix[i-1][j], matrix[i][j-1]), matrix[i-1][j-1]);

            if(stripe[i] == favorite[j]) matrix[i][j] = maxlen+1;
            else matrix[i][j] = maxlen;
        }
	}

	return matrix[l][m];
}

int main(){
    cin >> n >> m;

	for(int i = 1; i <= m; ++i)
		scanf("%d", favorite+i);

	cin >> l;
	for(int i = 1; i <= l; ++i)
		scanf("%d", stripe+i);

	cout << lcs();

	return 0;
}