Pagini recente » Monitorul de evaluare | Diferente pentru concursuri intre reviziile 182 si 128 | Cod sursa (job #2702675) | Monitorul de evaluare | Cod sursa (job #2151410)
#include <fstream>
using namespace std;
ifstream input("cmlsc.in");
ofstream print("cmlsc.out");
int DP[1025][1025],LCS[1025];
int A[1025],B[1025];
int i,j,n,m,lg;
void Read(){
input>>m>>n;
for(i=1;i<=m;i++)input>>A[i];
for(i=1;i<=n;i++)input>>B[i];
}
void Rezolvare(){
for(i=1;i<=m;i++)
for(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]);
}
print<<DP[m][n]<<'\n';
lg=DP[m][n];
for(i=m;i>=1;i--)
for(j=n;j>=1;j--)
if(DP[i][j]==lg && A[i]==B[j])
LCS[lg--]=A[i];
for(i=1;i<=DP[m][n];i++)print<<LCS[i]<<" ";
}
int main(){
Read();
Rezolvare();
return 0;
}