Cod sursa(job #2197525)

Utilizator ssebiStanciu Sebastian ssebi Data 22 aprilie 2018 14:17:48
Problema Subsecventa de suma maxima Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
#define NMax 1027
void subsir(int a[NMax][NMax],int v1[NMax], int v2[NMax],int x,int y)
{
    int v[NMax];
    int t=0;
    int i,j;
    for(i=0;i<=x;++i)
        for(j=0;j<=y;++j)
    {
        if(i==0||j==0)
            a[i][j]=0;
        else if(v1[i]==v2[j])
            a[i][j]=a[i-1][j-1]+1;
            else a[i][j]=max(a[i-1][j],a[i][j-1]);
    }
    fout<<a[x][y]<<endl;
   int s=1;
   int j1=y;
   int i1=x;
    while(s)
    {
        if(a[i1-1][j1]==a[i1][j1])
        {
            i1=i1-1;
            j1=j1;
        }
        else if(a[i1][j1-1]==a[i1][j1])
            {
                i1=i1;
            j1=j1-1;
           }
       else
           {
            j1=j1-1;
            i1=i1-1;
            v[t]=v2[j1+1];
            t++;
           }
           if(a[i1][j1]==0)
            s=0;

    }
    for(i=t-1;i>=0;--i)
        fout<<v[i]<<' ';

}
int main()
{
    int x,v1[NMax],v2[NMax],y,a[NMax][NMax];
    fin>>x>>y;
    int i,j;
    for(i=1;i<=x;++i)
        fin>>v1[i];
    for(i=1;i<=y;++i)
        fin>>v2[i];
    subsir(a,v1,v2,x,y);
    return 0;
}