Pagini recente » Cod sursa (job #2208304) | Cod sursa (job #613136) | Cod sursa (job #406860) | Cod sursa (job #1388610) | Cod sursa (job #819088)
Cod sursa(job #819088)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int debug = 0;
int max(int a, int b) {
return (a > b ? a : b);
}
void printVector(vector<int> &v) {
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
printf("%d ", *it);
}
printf("\n");
}
vector<int> *longestSubseq(vector<int> &A, vector<int> &B) {
//A.insert(A.begin(), 0);
//B.insert(B.begin(), 0);
int M = A.size(), N = B.size();
vector<int> *result = new vector<int>;
vector< vector<int> > D(M, vector<int>(N, 0));
for (int i = 1; i < M; ++i)
for (int j = 1; j < N; ++j) {
if (A[i-1] == B[j-1]) {
if (debug) {printf("A[%d] == B[%d]\n", i, j);}
D[i][j] = 1 + D[i-1][j-1];
} else {
D[i][j] = max(D[i-1][j], D[i][j-1]);
}
}
if (debug) {
printf("A: "); printVector(A);
printf("B: "); printVector(B);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
printf("%d ", D[i][j]);
}
printf("\n");
}
}
for (int i = M - 1, j = N - 1; i; ) {
if (debug) {printf("i=%d, j=%d, A[i]=%d, B[j]=%d, D[i][j]=%d", i, j, A[i], B[j], D[i][j]);}
if (i == M || j == N) {
printf("!!! i=%d, j=%d\n", i, j);
}
if (A[i-1] == B[j-1]) {
if (debug) {printf("\tA[i] == B[j]");}
result->push_back(A[i-1]);
--i;
--j;
} else if (D[i-1][j] < D[i][j-1]) {
--j;
} else {
--i;
}
if (debug) {printf("\n");}
}
reverse(result->begin(), result->end());
if (debug) {printf("result: "); printVector(*result);}
return result;
}
int main() {
int M, N, tmp;
freopen("cmlsc.in", "r", stdin);
freopen("cmlsc.out", "w", stdout);
vector<int> A, B;
scanf("%d %d", &M, &N);
for (int i = 1; i <= M; ++i) {
scanf("%d", &tmp);
A.push_back(tmp);
}
for (int i = 1; i <= N; ++i) {
scanf("%d", &tmp);
B.push_back(tmp);
}
vector<int> *subseq = longestSubseq(A, B);
printf("%d\n", (int)subseq->size());
for (int i = 0, size = subseq->size(); i < size; ++i) {
printf("%d ", (*subseq)[i]);
}
printf("\n");
}