Pentru a nu intra în faliment, noua conducere a fabricii OLDTRICK a derulat un plan de restructurate în n etape. În fiecare etapă, fabrica a împrumutat de la bancă o sumă a_i. La terminarea celor n etape, fabrica a început să restituie împrumuturile astfel: primul împrumut a fost restituit, apoi conducerea fabricii a constatat că nu-și poate achita toate datoriile și a hotărât să restituie doar sume care nu au fost împrumutate în etape succesive. Să se determine care este suma totală maximă pe care o poate restitui fabrica.

Cerința

Cunoscând n – numărul de etape, a_i – suma împrumutată în etapa i (1 ≤ i ≤ n), să se determine care este suma totală maximă pe care o poate restitui fabrica, știind că primul împrumut este întotdeauna achitat.

Date de intrare

Fișierul de intrare datorii.in conține pe prima linie n numărul de etape iar pe următoarea linie n valori naturale nenule a₁, a₂, …, a_n reprezentând sumele împrumutate în fiecare etapă.

Date de ieșire

Fișierul de ieșire datorii.out va conține pe prima linie un număr reprezentând suma totală maximă pe care o poate restitui fabrica.

Restricții și precizări

1 ≤ n ≤ 1000
1 ≤ a_i ≤ 10000

Exemplul 1:

datorii.in

6 
1 3 6 2 4 3

datorii.out

Exemplul 2:

datorii.in

4
2 1 4 100

datorii.out

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

#include <bits/stdc++.h>
using namespace std;

int a[10005], dp[10005], n;
/// dp[i] = suma maxima obtinuta din a[1..i]

int main()
{
    int i;
    ifstream fin("datorii.in");
    ofstream fout("datorii.out");
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];

    dp[2] = dp[1] = a[1];
    ///dp[2] = max(a[1], a[2]);
    for (i = 3; i <= n; i++)
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
    fout << dp[n] << "\n";
    fin.close();
    fout.close();
    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 #2704 datorii

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