Pagini recente » Cod sursa (job #1883604) | Cod sursa (job #1018851) | Cod sursa (job #1264362) | Cod sursa (job #550974) | Cod sursa (job #2718196)
#include <fstream>
#include <vector>
const int N = (1<<10)+1;
int dp[N][N];
std::pair<int, int>prev[N][N];
int main() {
std::ifstream fin("cmlsc.in");
std::ofstream fout("cmlsc.out");
int n, m;
fin>>n>>m;
std::vector<int>a(n+1), b(m+1);
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] = dp[i-1][j], prev[i][j] = {i-1, j};
if(dp[i][j]<dp[i][j-1]) dp[i][j] = dp[i][j-1], prev[i][j] = {i, j-1};
if(a[i] == b[j])
if(dp[i][j] < dp[i-1][j-1] + 1) dp[i][j] = dp[i-1][j-1] + 1, prev[i][j] = {i-1, j-1};
}
fout<<dp[n][m]<<"\n";
std::vector<int>ans;
int x = n, y = m;
while(x and y) {
if(prev[x][y].first==x-1 and prev[x][y].second==y-1) ans.push_back(a[x]);
x = prev[x][y].first, y = prev[x][y].second;
}
for(int i=ans.size()-1;i>=0;i--) fout<<ans[i]<<" ";
}