Pagini recente » Cod sursa (job #1964716) | Istoria paginii runda/concurs_fara_nume./clasament | Istoria paginii runda/preoji2014_0_10 | Cod sursa (job #1665585) | Cod sursa (job #2672317)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int oua[100005];
int n;
int get_ans(int st,int dr)
{
vector<int>dp;
///Se adauga 3 elemente egale cu 0 in dp
dp.push_back(0);///raspunsul creat anterior caruia i se poate adauga suma urmatoarelor 2 sectoare
dp.push_back(0);
dp.push_back(0);///ultimul raspuns creat
int pos=3;///numarul de elemente adaugate in dp
for(int i=st+1;i<=dr;i++, pos++)
{
int suma_perechii=oua[i]+oua[i-1];///incercam sa adaugam ouale din sectoarele i-1 si i
dp.push_back(max(dp[pos-1],dp[pos-3]+suma_perechii));///adaugam in dp raspunsul creat pana la sectorul i
}
return dp.back();///returnam raspunsul
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>oua[i];
///Ne usuram problema prin privirea acesteia ca si un simplu sir
int ans=oua[1]+oua[n]+get_ans(3,n-2);///ne initializam raspunsul cu cazul in care luam perechea (n,1)
ans=max(ans,get_ans(1,n-1));///luam in considerare faptul ca sectorul n ar putea fi blocat
ans=max(ans,get_ans(2,n));///luam in considerare faptul ca sectorul 1 ar putea fi blocat
fout<<ans;
return 0;
}