Cod sursa(job #2468633)

Utilizator q1e123Solca Robert-Nicolae q1e123 Data 5 octombrie 2019 18:29:33
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>

#define MAX 1025
int m,n;
int a[MAX],b[MAX];
int dp[MAX][MAX];
int counter;
int sol[MAX];
int max(int x,int y){
        if(x>y) return x;
        else return y;
}

void dynamic(){
        for(int i=1;i<=m;++i){
                for(int 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]);
                        }
                }
        }
}

void build(){
        int i,j,;
        i=m;
        j=n;
        while(i){
                if(a[i]==b[j]){
                        sol[++counter]=a[i];
                        --i;--j;
                }else	if(dp[i-1][j]<dp[i][j-1]) j--;
                else i--;
        }
}

void write(){
        printf("%d\n",counter);
        for(int i = 1;i<=counter;++i) printf("%d ", sol[i]);
}

void read(){

        scanf("%d %d",&m,&n);


        for(int i = 1; i<=m;++i){
                scanf("%d",&a[i]);
        }

        for(int i = 1; i<=n;++i){
                scanf("%d",&b[i]);
        }

}

int main() {
        freopen("cmlsc.in","r",stdin);
        freopen("cmlsc.out","w",stdout);

        read();
        dynamic();
        build();
        write();
        return 0;
}