Pagini recente » Cod sursa (job #675765) | Cod sursa (job #474839) | Cod sursa (job #3151303) | Cod sursa (job #739762) | Cod sursa (job #3252117)
#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]