Cerința

Se citeşte n şi un vector v cu n numere naturale. Să se calculeze numărul total S de subşiruri strict crescătoare care se pot forma folosind aceste numere.

Date de intrare

Fișierul de intrare nrsubsircresc.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire nrsubsircresc.out va conţine numărul S cu semnificaţia din enunt.

Restricții și precizări

1 ≤ n ≤ 300
v[i] ≤ 1.000.000, pentru oricare 1 ≤ i ≤ n
S ≤ 10¹⁸

Exemplu

nrsubsircresc.in

6
5 2 6 1 1 8

nrsubsircresc.out

Explicație

Cele 15 subşiruri strict crescătoare sunt: {5}, {2}, {6}, {1}, {1}, {8}, {5, 6}, {5, 8}, {2, 6}, {2, 8}, {6, 8}, {1, 8}, {1, 8}, {5, 6, 8}, {2, 6, 8}.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema NrSubsirCresc :

// Back: 20p
// Pd: 100p

#include<fstream>
using namespace std;

#define dim 301

ifstream in("nrsubsircresc.in");
ofstream out("nrsubsircresc.out");

long long sol[dim]; /// sol[i] = nr. de subsiruri strict crescatoare care au ultimul element v[i]
long long v[dim];
long long n;

int main()
{
    long long i,j,s;

    //
    in>>n;
    for(i=0; i<n; ++i) in>>v[i];

    //
    for(i=0; i<n; ++i)
    {
        sol[i] = 1; /// v[i] de unul singur
        for(j=0; j<i; ++j)
            if(v[i] > v[j]) /// daca v[i] este mai mare decat un predecesor de-al sau
                sol[i] += sol[j]; /// acesta ii poate continua toate sirurile
    }

    s=0;
    for(i=0; i<n; ++i) s += sol[i];

    out<<s<<"\n";

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1342 NrSubsirCresc

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1342 NrSubsirCresc de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1342 NrSubsirCresc