Cod sursa(job #1808047)

Utilizator PondorastiAlex Turcanu Pondorasti Data 17 noiembrie 2016 11:09:50
Problema Oo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int Dinamica(int a, int b);
const int NMAX=100000;
int d[NMAX+5],v[NMAX+5],n,m1,m2,m3,m;
int main()
{
    ifstream cin("oo.in");
    ofstream cout("oo.out");
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>v[i];}
    v[n+1]=v[1];
    m1=Dinamica(2,n);
    m2=Dinamica(1,n-1);
    m3=Dinamica(3,n-2);
    if(n==3)
        m=max(max(v[1]+v[2],v[2]+v[3]),v[3]+v[1]);
    else
        m=max(max(m1,m2),m3);
    cout<<m;
    return 0;
}
int Dinamica(int a, int b) {
    int ma=0;
    d[a]=0;
    d[a+1]=v[a+1]+v[a];
    d[a+2]=max(v[a]+v[a+1],v[a+1]+v[a+2]);
    for(int i=a+3;i<=b;i++) {
        d[i]=max(d[i-1],d[i-3]+v[i]+v[i-1]);}
    return d[b];
}