Pagini recente » Cod sursa (job #3362857) | Cod sursa (job #3362380) | Cod sursa (job #3361472) | Cod sursa (job #3361269) | Cod sursa (job #3362733)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("cmlsc.in");
ofstream out ("cmlsc.out");
int m, n;
int a[1030], b[1030];
int dp[1030][1030];
vector <int> v;
int main()
{
in >> m >> n;
for (int i = 1; i <= m; i++)
{
in >> a[i];
}
for (int i = 1; i <= n; i++)
{
in >> b[i];
}
for (int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if(a[i] == b[j])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
} else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
out << dp[m][n] << "\n";
int i = m, j = n;
while (i > 0 && j > 0)
{
if (a[i] == b[j])
{
v.push_back(a[i]);
i--;
j--;
} else if (dp[i - 1][j] >= dp[i][j - 1])
{
i--;
} else
{
j--;
}
}
for (int k = v.size() - 1; k >= 0; k--)
{
out << v[k] << " ";
}
return 0;
}