Cod sursa(job #187783)
Utilizator | Data | 5 mai 2008 13:47:20 | |
---|---|---|---|
Problema | Cel mai lung subsir comun | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.29 kb |
#include<fstream>
using namespace std;
ifstream fin ("cmlsc.in");
ofstream fout ("cmlsc.out");
int d[1024][1024],s[1024],p,i,k;
int main ()
{
int n,m;
fin>>n>>m;
int a[n],b[m];
for(i=1;i<=n;i++)
fin>>a[i];
for(i=1;i<=m;i++)
fin>>b[i];
for(i=1;i<=n;i++)
{
for(k=1;k<=m;k++)
{
if(a[i]==b[k])
d[i][k]=1+d[i-1][k-1];
else
if(d[i-1][k]>d[i][k-1])
d[i][k]=d[i-1][k];
else
d[i][k]=d[i][k-1];
}}
for (i=n,k=m;i;)
if (a[i]==b[k])
{s[++p]=a[i];
--i;
--k;
}
else if (d[i-1][k]<d[i][k-1])
--k;
else
--i;
fout<<p<<"\n";
for(i=p;i>=1;i--)
fout<<s[i]<<" ";
fout<<"\n";
for(i=1;i<=n;i++)
{ for(k=1;k<=m;k++)
fout<<d[i][k]<<" ";
fout<<"\n";
}
return 0;
}