Cod sursa(job #3252117)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 28 octombrie 2024 16:39:53
Problema Oo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 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[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-1]);
    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 nu le iau pe primul si pe ultimul

///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]