👤
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 :

ANTIEAGLESDAVIDSVIZ
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 pentru vizita pe platforma noastră dedicată Informatică. Sperăm că informațiile prezentate v-au fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Așteptăm cu entuziasm să reveniți și vă invităm să ne adăugați la lista de favorite!


Viz Lesson: Alte intrebari