Pagini recente » Cod sursa (job #2201945) | Cod sursa (job #2655667) | Cod sursa (job #301366) | Monitorul de evaluare | Cod sursa (job #1642785)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define NMax 1025
ifstream f("cmlsc.in");
ofstream g("cmlsc.out");
int n, m;
vector<short> A;
vector<short> B;
short C[NMax][NMax];
vector<short> sol;
void dodp() {
for (int i=0;i<=n;i++)
C[0][i] = 0;
for (int i=0;i<=m;i++)
C[i][0] = 0;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (A[i] == B[j]) {
C[i][j] = 1+C[i-1][j-1];
} else {
C[i][j] = max(C[i][j-1], C[i-1][j]);
}
}
}
g<<C[n][m]<<'\n';
int i=n;
int j=m;
while (i > 1 || j > 1) {
if (C[i][j] == 1+C[i-1][j-1]) {
sol.pb(A[i]);
i--; j--;
} else {
if (C[i][j] == C[i-1][j])
i--;
else
j--;
}
}
for (int p=sol.size()-1;p>=0;p--) {
g<<sol[p]<<' ';
}
g<<endl;
}
void read() {
f>>n>>m;
A.pb(0); B.pb(0);
for (int i=1;i<=n;i++) {
int x; f>>x;
A.pb(x);
}
for (int i=1;i<=m;i++) {
int x; f>>x;
B.pb(x);
}
}
int main() {
read();
dodp();
f.close(); g.close();
return 0;
}