👤
a fost răspuns

https://www.pbinfo.ro/?pagina=probleme&id=2684
Se dă un șir de n numere naturale. Șirul poate fi partiționat în mai multe moduri într-un număr de subșiruri strict crescătoare. De exemplu, șirul 4 6 2 5 8 1 3 7 poate fi partiționat astfel: 4 6 8 (primul subșir), 2 5 7 (al doilea) și 1 3 (al treilea). O altă modalitate este formând patru subșiruri: 4 5 7, 6 8, 2 3 și 1.


Cum se rezolva asta ?

Răspuns :

Răspuns:

#include <iostream>

using namespace std;

int n, v[1001],l[1001],siruri,f[50000],i,j,k=1;

long long mx=-1000000000;

void citire(int v[],int &n)

{

   int i;

   cin>>n;

   for(i=1; i<=n; i++)

       cin>>v[i];

}

int main()

{

   citire(v,n);

   for(i=1; i<=n; i++)

   {

       mx=v[i];

       f[v[i]]++;

       if(f[v[i]]<2)

       {

           l[k++]=v[i];

           for(j=i+1; j<=n; j++)

           {

               if(v[j]>=mx)

               {

                   f[v[j]]++;

                   if(f[v[j]]<2 || v[j]==mx)

                   {

                       mx=v[j];

                       l[k++]=v[j];

                   }

               }

           }

           siruri++;

       }

   }

   cout<<siruri<<endl;

   for(i=1;i<k;i++)

      cout<<l[i]<<' ';

   return 0;

}

Explicație:

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari