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.
Cerința
Să se determine numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.
Date de ieșire
Programul va afișa pe ecran numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.
Restricții și precizări
1 ≤ n ≤ 100.000
cele n numere citite vor fi mai mici decât 100.000
Un subșir se obține dintr-un șir prin eliminarea a zero, unul, sau mai multe elemente.
Răspunsuri la întrebare
Răspuns de
0
Si eu am nevoie de ajutor tot la aceasta problema.
Momentan am gasit asta, de 90 de puncte, sper ca poate fi de folos pt cei care ne vor ajuta.
Anexe:
jtunde:
Multumesc. Intre timp am reusit.
#include
using namespace std;
int v[100001],t[100001];
int main()
{int n,i,j,k=0,e,u,p=-1;
cin>>n;
for(i=0;i cin>>t[i];
v[k++]=t[0];
for(i=1;i if(t[i]<=v[k-1])v[k++]=t[i];
else{e=0;
u=k-1;
p=0;
while(e<=u){
j=(e+u)/2;
if(v[j] p=j;
u=j-1;
}
else e=j+1;
}
v[p]=t[i];
}
}
cout<}
using namespace std;
int v[100001],t[100001];
int main()
{int n,i,j,k=0,e,u,p=-1;
cin>>n;
for(i=0;i cin>>t[i];
v[k++]=t[0];
for(i=1;i if(t[i]<=v[k-1])v[k++]=t[i];
else{e=0;
u=k-1;
p=0;
while(e<=u){
j=(e+u)/2;
if(v[j] p=j;
u=j-1;
}
else e=j+1;
}
v[p]=t[i];
}
}
cout<}
Mersi !
Alte întrebări interesante
Limba română,
8 ani în urmă
Matematică,
8 ani în urmă
Limba română,
8 ani în urmă
Matematică,
8 ani în urmă
Informatică,
8 ani în urmă
Limba română,
9 ani în urmă