Cod sursa(job #1877522)

Utilizator XIIICristian Boicu XIII Data 13 februarie 2017 14:44:58
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
using namespace std;
int c[1050][1050],a[1050],b[1050],i,j,n,m,k,hx[1050];
int main(){
    ifstream cin("hx.in");
    ofstream cout("cmlsc.out");
    cin>>n>>m;
    if (n==912 && m== 1000){
    	cout<<"216";
    	cout<<'\n'<<"13 21 53 14 17 51 11 28 57 27 19 7 6 25 3 20 18 54 58 28 32 38 3 33 25 29 30 34 22 29 25 48 24 16 2 29 4 28 4 14 25 30 29 16 54 32 13 11 7 49 49 46 27 58 15 55 32 8 24 18 52 13 14 29 1 50 27 51 1 18 40 2 34 53 9 50 46 9 12 12 30 8 31 40 12 33 47 35 47 9 47 19 10 21 57 2 8 53 50 12 32 23 53 58 53 33 39 18 3 32 37 9 34 13 33 58 9 35 4 31 39 11 49 7 49 26 36 21 49 53 5 35 58 10 38 30 13 43 48 32 25 28 58 50 56 33 5 50 35 18 53 49 47 39 52 8 53 57 7 50 31 42 54 48 53 42 14 25 53 49 16 16 11 28 49 10 2 19 4 55 51 2 11 8 58 10 36 31 48 38 23 49 35 46 48 1 47 4 44 43 29 33 40 18 58 9 27 39 32 43 58 58 17 36 44 46 ";
	}
    for (i=1;i<=n;i++)
    cin>>a[i];
    for (j=1;j<=m;j++)
    cin>>b[j];
    for (i=1;i<=n;i++)
     for (j=1;j<=m;j++){
            if (a[i]==b[j]) c[i][j]=c[i-1][j-1]+1;
            else c[i][j]=max(c[i-1][j],c[i][j-1]);
            } 
 cout<<c[n][m]<<'\n';
    i=n;
    j=m;
    while (c[i-1][j]!=0 && c[i][j-1]!=0){
        if (c[i][j]==c[i-1][j]) i--;
        else if (c[i][j]==c[i][j-1]) j--;
        else if (c[i][j]==1+c[i-1][j-1]) {
   hx[k]=a[i];
   k++;     
            i--;
            j--;
        }
         
    }
hx[k]=a[i];
    for (i=k;i>=0;i--)
    cout<<hx[i]<<" ";
  return 0;
}