# PBinfo #1342 – NrSubsirCresc – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 ≤ 1018

Exemplu:
nrsubsircresc.in

6
5 2 6 1 1 8
nrsubsircresc.out

15
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}.

## Cod sursă C++

```cpp
// 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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1342)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1342/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1342/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)