Mai intai trebuie sa te autentifici.
Cod sursa(job #1168856)
| Utilizator | Data | 9 aprilie 2014 19:13:40 | |
|---|---|---|---|
| Problema | Cel mai lung subsir comun | Scor | 10 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.92 kb |
//#include <iostream>
#include <fstream>
using namespace std;
int n,m,a[1024],b[1024],dp[1024][1024],v[1024];
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int main(){
int i,j;
fin >> m >> n;
for(i=1;i<=m;i++)
fin >> a[i];
for(i=1;i<=n;i++)
fin >> b[i];
fin.close();
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]);
}
fout << dp[m][n]<<"\n";
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++)
if(dp[i][j] != dp[i][j-1] && dp[i][j] != 0 && v[j] == 0)
{
v[j]++;
fout << b[j]<<" ";
}
fout << "\n";
// for(i = 1; i <= m; i++)
// {
// for(j = 1; j<=n;j++)
// cout << dp[i][j]<<" ";
// cout <<"\n";
// }
fout.close();
return 0;
}
