Cod sursa(job #3252121)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 28 octombrie 2024 16:52:38
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>

using namespace std;
ifstream cin("oo.in");
ofstream cout("oo.out");
int n,v[100005],dp[100005],maxi;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    ///cazul 1
    dp[1]=0;
    dp[2]=0;
    dp[3]=v[2]+v[3];
    for(int i=4;i<=n;i++)
        dp[i]=max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
    maxi=max(maxi,dp[n]);

    ///cazul 2
    dp[1]=0;
    dp[2]=v[1]+v[2];
    for(int i=3;i<=n-1;i++)
        dp[i]=max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
    maxi=max(maxi,dp[n-1]);

    ///cazul 3

    dp[2]=0;
    dp[3]=0;
    dp[4]=v[3]+v[4];
    for(int i=5;i<=n-2;i++)
         dp[i]=max(dp[i-1],dp[i-3]+v[i-1]+v[i]);
    maxi=max(maxi,dp[n-2]+v[1]+v[n]);
    cout<<maxi;
    return 0;
}
///dp[i]=nr maxim de oua pe care le poate strange din primele i elemente
///avem mai multe cazuri cum incepem dinamica:
///1 nu-l iau pe primul
///2 nu-l iau pe ultimul
///3 le iau pe primul si pe ultimul=>al doilea si penultimul nu se iau

///dp[i]=max(dp[i-1],dp[i-3]+v[i-1]+v[i])
///nu-l iau pe v[i] in calcul dp[i]=dp[i-1]
///sau in iau in calcul dp[i]=dp[i-3]+v[i-1]+v[i]