Probleme de informatica - enunturi si rezolvari

Se citeste un numar n si apoi 2 siruri formate din cate n cuvinte fiecare. Primul sir de cuvinte stabileste ordinea initiala, iar al doilea este o permutare a primului (aceleasi cuvinte, dar in alta ordine).
Gasiti cel mai lung subsir de cuvinte din cel de-al doilea sir care are proprietatea ca are cuvintele in ordinea din primul sir de cuvinte. Se va afisa numarul maxim de cuvinte si apoi cuvintele.
Daca exista mai multe subsiruri de lungime maxima se va afisa unul dintre ele.
Exemplu:
date.in
5
platon kant marx stalin havel
marx stalin kant platon havel
date.out
3
marx stalin havel

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n, A[10000], L[10000], maxt, pm;
char O[10000][50], S[10000][50];

void citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++) fin>>O[i];
    for(i=1;i<=n;i++) fin>>S[i];
}

int poz(int k)
{
    int i;
    for(i=1;i<=n;i++)
       if(strcmp(O[i],S[k])==0) return i;
    return 0;
}

void afis(int k, int m)
{
   if(m>0)
   {
        int i=k-1;
        while(L[i]!=m-1) i--;
        afis(i,m-1);
        fout<<O[A[k]]<<" ";
   }
}

int main()
{
    int i,j,maxx;
    citire();
    for(i=1;i<=n;i++) A[i]=poz(i);
    L[1]=1;
    for(i=2;i<=n;i++)
    {
        maxx=0;
        for(j=1;j<i;j++)
           if(A[j]<=A[i] && L[j]>maxx) maxx=L[j];
        L[i]=maxx+1;
        if(L[i]>maxt)
                {
                    maxt=L[i];
                    pm=i;
                }
    }
    fout<<maxt<<endl;
    afis(pm,maxt);
    return 0;
}

21 nov 2024

Site-ul conține 884 de probleme rezolvate