Cod sursa(job #2749299)

Utilizator mariusn01Marius Nicoli mariusn01 Data 6 mai 2021 11:33:29
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
/// oo greedy

#include <fstream>

using namespace std;
int v[100010];
int D[100010];
int n, sol, i;

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

    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i];
    }

/**
    D[i] = suma maxima folosind primele i elemente din sir
    de regula la dinamica ma folosesc de valori ale structurii calulate deja
    definitiv anterior, apoi mai iau in calcul elemente in plus fata de cele
    incluse in valorile calculate
    - pentru pozitia i am 2 variante:
            a) nu iau in calcul valoarea v[i] si atunci pentru pozitia i
                conteaza D[i-1]
            b) iau in calcul valoarea i odata cu valoarea i-1 (sunt obligat sa iau
                cate doua valori vecine deodata)
            D[i] = maximul dintre cele 2 variante
            D[i] = maxim (  D[i-1], v[i]+v[i-1]+D[i-3]  )
    - Ramane de stabilit cum facem initializarea
    - De vazut cum tratam cazul cu sir circular (propun sa facem dinamica de mai multe ori)
**/

/**
    Cazul 1 nu aleg pe primul
    facem dinamica si luam in calcul la solutie pe D[n]
**/
/// mai jos sunt initializati neluand in calcul primul element
    D[1] = 0;
    D[2] = 0;
    D[3] = v[2]+v[3];
    for (i=4;i<=n;i++)
        D[i] = max(D[i-1], D[i-3] + v[i]+v[i-1]);
    sol = D[n];
/**
    Cazul 2 nu aleg pe ultimul
    fac initializarile diferit luand in calcul si ca il pot alege pe primul
    iau in calcul la solutie doar pe D[n-1]
**/
    D[1] = 0;
    D[2] = v[1]+v[2];
    D[3] = max(v[2]+v[3], v[1]+v[2]);
    for (i=4;i<n;i++)
        D[i] = max(D[i-1], D[i-3] + v[i]+v[i-1]);
    sol = max(sol, D[n-1]);

/**
    Cazul 3 aleg pe primul si pe ultimul
    inseamna ca nu pot alege pe al doilea si nici pe penultimul
    /// fac initializarile stiind ca al doilea nu poate fi ales
**/
    D[2] = 0;
    D[3] = 0;
    D[4] = v[3]+v[4];
    for (i=5;i<=n-2;i++)
        D[i] = max(D[i-1], D[i-3] + v[i]+v[i-1]);

    sol = max(sol, D[n-2] + v[1] + v[n]);

    fout<<sol;
    return 0;
}