Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar dori să afle într-un mod inedit conținutul unui fișier de intrare aferent unei probleme de concurs, în care sunt scrise elementele unui șir p de N numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de C(i,j) bănuți pentru a-i divulga suma numerelor din șirul p cu indici în intervalul [i, j], anume p_i + p_i+1 + ... + p_j.

Cerința

Dându-se valoarea lui N și toate valorile C(i,j) cu 1 ≤ i ≤ j ≤ N, determinați costul total minim pe care trebuie să-l plătească Alfredo pentru a afla toate elementele șirului p.

Date de intrare

În fișierul oracol.in se află pe prima linie numărul natural N. Pe următoarele N linii se află taxele percepute de Gustavo astfel: pe linia i+1 se vor afla N-i+1 numere naturale separate prin câte un spațiu, reprezentând în ordine costurile C(i,i), C(i,i+1), …, C(i,N).

Date de ieșire

Fișierul de ieșire oracol.out va conține pe prima linie un singur număr care reprezintă costul total minim pe care trebuie să-l plătească Alfredo pentru a afla șirul p.

Restricții și precizări

1 ≤ N ≤ 1000;
pentru orice 1 ≤ i ≤ j ≤ N se garantează 0 ≤ C(i,j) ≤ 1.000.000;
pentru teste în valoare de 48 puncte 1 ≤ N ≤ 250.

Exemplu

oracol.in

oracol.out

Explicație

Costul total minim este 6 și se obține astfel:
Cu un cost de valoare C(1,3) = 1 putem afla suma p₁ + p₂ + p₃.
Cu un cost de valoare C(3,3) = 2 putem afla valoarea lui p₃.
Cu un cost de valoare C(2,3) = 3 putem afla suma p₂ + p₃.
Din acestea putem afla exact toate elementele șirului p.

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

#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

struct Edge {
    int from, to, cost;
    bool operator<(const Edge& e) const {
        return cost < e.cost;
    }
};

class DSU {
public:
    DSU(int n):
        f(n) {
        for (int i = 0; i < n; ++i) {
            f[i] = i;
        }
    }

    int& operator[](int x) {
        int y, p;
        for (y = x; y != f[y]; y = f[y]);
        for (; x != y; x = p) {
            p = f[x];
            f[x] = y;
        }
        return f[y];
    }
private:
    vector<int> f;
};

int main() {
    ifstream fin("oracol.in");
    ofstream fout("oracol.out");

    int n;
    fin >> n;

    vector<Edge> edges;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int cost;
            fin >> cost;
            edges.push_back(Edge{i, j, cost});
        }
    }
    sort(edges.begin(), edges.end());
    DSU f(n + 1);
    int64_t ans = 0;
    for (const Edge& e: edges) {
        if (f[e.from] != f[e.to]) {
            ans += e.cost;
            f[e.from] = f[e.to];
        }
    }
    fout << ans << '\n';
}

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 #3061 oracol

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3061 oracol 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 #3061 oracol