👤
a fost răspuns

Se considera numarul n si un vector v cu n elemente.
Construiti vectorul sol, cu următoarea semnificaţie: sol[i] va reţine numărul de subşiruri de elemente consecutive, ordonate strict crescător, care se termină cu i. Calculati suma tuturor elementelor vectorului sol.

Răspuns :

ANTIEAGLESDAVIDSZE
Tocmai am realizat ca sol[i] retine subsirurile pana in POZITIA i si nu pana la valoarea i . Problema a devenit astfel simpla ;)

===================================================

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 100005;

int n, sol_final = 1;
int v[NMAX], sol[NMAX];
vector<pair<int,int>> perechi;

int main()
{
    int suma;

    cin >> n;
    for(int i=1; i<=n; i++) cin >> v[i];

    for(int i=1; i<=n; i++) perechi.push_back(make_pair(v[i], i));
    sort(perechi.begin(), perechi.end());

    for(auto x : perechi) {
        suma = 0;
        for(int j=1; j<=x.second; j++) {
            if(x.first == v[j]) continue;
            else suma += sol[j];
        }
        sol[x.second] = 1 + suma;
    }

    for(int i=2; i<=n; i++) {
        sol[i] += sol[i-1];
        sol_final += sol[i];
    }

    cout << sol_final << '\n';
}

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de ajutor, nu ezitați să ne contactați. Vă așteptăm cu drag data viitoare și vă încurajăm să ne salvați în lista de favorite!


Ze Questions: Alte intrebari