Pagini recente » Cod sursa (job #2400666) | Cod sursa (job #1278868) | Cod sursa (job #1906997) | Cod sursa (job #677981) | Cod sursa (job #1522942)
#include <cstdio>
#include <algorithm>
#define NMAX 1027
#define in "cmlsc.in"
#define out "cmlsc.out"
#define shd short int
using namespace std;
int n1, n2;
shd v1[NMAX], v2[NMAX], dp[NMAX][NMAX];
inline void dinamica()
{
for(int i = 1; i<= n1; ++i)
{
for(int j = 1; j<= n2; ++j)
{
if(v1[i] == v2[j]) {dp[i][j] = dp[i-1][j-1]+1; continue;}
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
void reconstituire(const int &x, const int &y)
{
if(dp[x][y] == 0) return ;
if(dp[x-1][y-1] == dp[x][y])
{
reconstituire(x-1, y-1);
return ;
}
if(dp[x-1][y] > dp[x][y-1])
{
reconstituire(x-1, y);
return ;
}
if(dp[x][y-1] > dp[x-1][y])
{
reconstituire(x, y-1);
return ;
}
if(dp[x-1][y-1] == dp[x][y] - 1 && dp[x-1][y-1] == dp[x][y-1])
{
reconstituire(x-1, y-1);
printf("%d ", v1[x]);
return ;
}
reconstituire(x-1, y);
return ;
}
int main()
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
scanf("%d %d", &n1, &n2);
for(int i = 1; i<= n1; ++i) scanf("%hd", &v1[i]);
for(int i = 1; i<= n2; ++i) scanf("%hd", &v2[i]);
dinamica();
printf("%hd\n", dp[n1][n2]);
reconstituire(n1, n2);
printf("\n");
return 0;
}