Pagini recente » Cod sursa (job #2104115) | Cod sursa (job #2806259) | Cod sursa (job #2929541) | Cod sursa (job #2856805) | Cod sursa (job #3281929)
// dinamica circulara
/// (i, i+1) -> i - 1 & i + 2
/// (1, 2) -> n & 3
/// => (n-1, n) -> n - 2 & 1
/// Se observa ciclu in graful depenentelor
/*
dp[i] = max(dp[i-1], dp[i-3]) + (a[i] + a[i-1])
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
// solve calculează numărul maxim de ouă pe care le poate aduna fermierul într-un interval liniar
// [1, n], [2, n + 1], [3, n + 2]
int v[100005];
int n, add;
int dp[100006];
int solve(int start, int end)
{
for (int i = 1; i <= n + 1; i++)
dp[i] = 0;
for (int i = start + 1; i <= end + start + 1; i++)
{
add = 0;
if (i >= 4)
{
add = dp[i - 3];
}
dp[i] = std::max(dp[i - 1], v[i] + v[i - 1] + add);
}
return dp[start + n - 2];
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> v[i];
}
v[n + 1] = v[1];
int rez = std::max(solve(1, n), std::max(solve(2, n), solve(3, n)));
fout << rez;
return 0;
}