Pagini recente » Cod sursa (job #532513) | Cod sursa (job #2871090) | Cod sursa (job #567738) | Cod sursa (job #1950715) | Cod sursa (job #1099062)
#include <iostream>
#include <stdio.h>
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
FILE *f1=freopen("cmlsc.in", "r", stdin);
FILE *f2=freopen("cmlsc.out", "w", stdout);
int n, m, a[1025], b[1025], l[1025][1025], dr[1025];
const int di[3]={-1, -1, 0}, dj[3]={0, -1, -1};
void cit()
{
scanf("%d%d", &n, &m);
for (int i=0; i<n; i++)
scanf("%d", &a[i]);
for (int j=0; j<m; j++)
scanf("%d", &b[j]);
}
int lmax()
{
for (int j=0; j<n; j++)
if (a[j]==b[j])
l[0][j]=1;
for (int i=0; i<m; i++)
if (a[i]==b[i])
l[i][0]=1;
for (int i=1; i<n; i++)
for (int j=1; j<m; j++)
{
int maxi=0;
for (int v=0; v<3; v++)
maxi=max(maxi, l[i+di[v]][j+dj[v]]);
l[i][j]=maxi;
if (maxi==l[i-1][j-1] && a[i]==b[j])
l[i][j]++;
}
return l[n-1][m-1];
}
void drum()
{
int i=n-1, j=m-1;
while (i!=0 || j!=0)
{
if (a[i]==b[j])
{
dr[++dr[0]]=a[i];
if (i>0)
i--;
if (j>0)
j--;
}
else if (l[i-1][j-1]>=l[i-1][j] && l[i-1][j-1]>=l[i][j-1])
{
if (i>0)
i--;
if (j>0)
j--;
}
else if (l[i-1][j]>=l[i-1][j-1] && l[i-1][j]>=l[i][j-1] && j-1>=0)
i--;
else if (i-1>=0)
j--;
}
if (a[i]==b[j])
dr[++dr[0]]=a[i];
for (int i=dr[0]; i>=1; i--)
printf("%d ", dr[i]);
}
void sol()
{
printf("%d\n", lmax());
drum();
}
int main()
{
cit();
sol();
return 0;
}