Cod sursa(job #2383416)

Utilizator MoisaRaduMoisa Alin Radu Andru MoisaRadu Data 19 martie 2019 14:23:12
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
/*
D[i] = suma din primele i cutii doar cu secvente de cate exact doua vecine
- pot gandi D[i] ca mai sus si obligatoriu cu ultima valoare aleasa
- pot gandi fara sa oblig sa fi fost aleasa ultima valoare
Sa analizam semnificatia lu D[i] in al doilea caz


D[i]
    - fie aleg din ultimele doua cutii, v[i]+v[i-1]+D[i-3]
    - nu iau din ultima cutie D[i-1]

    D[1] = 0;
    D[2] = v[1] + v[2];
    D[3] = max(v[1]+v[2], v[2]+v[3]);
    for (i=;i<=n;i++)
        D[i] = max(D[i-1], v[i]+v[i-1] + D[i-3]);

Pentru sir circular:
    1. Nu iau in calcul ultimul element la dinamica de mai sus
adica fac dinamica de mai sus si consider D[n-1]
    2. Nu iau in calcul primul element si inseamna ca fac initializarile altfel
D[1] = 0;
D[2] = 0;
D[3] = v[2]+v[3];
fac dinamica normal si iau in calcul pe D[n]
    3. Iau in calcul cazul cu primul si ultimul sigur in solutie
Deci nu voi lua nici pe v[2] nici pe v[n-1]
D[1] = 0;
D[2] = 0;
D[3] = 0;
D[n-2] + V[1]+V[n]
*/
#include <fstream>
using namespace std;

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

int D[100001],v[100001];
int n,sol,i;

int main(){
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    D[1]=0;
    D[2]=v[1]+v[2];
    D[3]=max(v[1]+v[2],v[2]+v[3]);
    for(i=4;i<n;i++)
        D[i]=max(D[i-1],v[i]+v[i-1]+D[i-3]);
    sol=D[n-1];
    D[1]=0;
    D[2]=0;
    D[3]=v[2]+v[3];
    for(i=4;i<=n;i++)
        D[i]=max(D[i-1],v[i]+v[i-1]+D[i-3]);
    sol=max(sol,D[n]);
    D[1]=0;
    D[2]=0;
    D[3]=0;
    for(i=4;i<n-1;i++)
        D[i]=max(D[i-1],v[i]+v[i-1]+D[i-3]);
    sol=max(sol,D[n-2]+v[1]+v[n]);
    fout<<sol;
    return 0;
}