Pagini recente » Cod sursa (job #2766100) | Cod sursa (job #2249155) | Cod sursa (job #1150545) | Cod sursa (job #3213659) | Cod sursa (job #3213688)
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
const int nmax = (1<<10) + 1;
int n , m , a[nmax] , b[nmax] , dp[nmax][nmax];
pii pre[nmax][nmax];
struct rem
{
int val , i , j;
};
rem best[nmax][nmax];
void rec(int x , int y)
{
if(x == y && x == 0) return;
rec(pre[x][y].first,pre[x][y].second);
fout << a[x] << ' ';
}
signed main()
{
fin >> n >> m;
for(int i = 1 ; i <= n ; ++i) fin >> a[i];
for(int i = 1 ; i <= m ; ++i) fin >> b[i];
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= m ; ++j) dp[i][j] = -1e9;
}
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= m ; ++j)
{
if(a[i] != b[j]);
else
{
int mx = -1e9;
if(i-1 >= 1 && j-1 >= 1) mx = best[i-1][j-1].val;
if(mx+1 > 1)
{
dp[i][j] = mx + 1;
pre[i][j] = {best[i-1][j-1].i,best[i-1][j-1].j};
}
else
{
dp[i][j] = 1;
pre[i][j] = {0,0};
}
dp[i][j] = max(1,mx+1);
}
int mx = dp[i][j];
pii to = {i,j};
if(i-1 >= 1 && best[i-1][j].val > mx)
{
mx = best[i-1][j].val;
to = {best[i-1][j].i,best[i-1][j].j};
}
if(j-1 >= 1 && best[i][j-1].val > mx)
{
mx = best[i][j-1].val;
to = {best[i][j-1].i,best[i][j-1].j};
}
best[i][j] = {mx,to.first,to.second};
}
}
cout << dp[n][m] << endl;
rec(n,m);
return 0;
}