Pagini recente » Cod sursa (job #1712113) | Monitorul de evaluare | Cod sursa (job #3327250) | Cod sursa (job #3306043) | Cod sursa (job #3341525)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <Vector>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
#define nmax 100005
int n, v[nmax], p[nmax], dp[nmax];
// Run DP on p[l..r], return best sum with no two chosen pairs within distance 2
int solve(int l, int r) {
if (l > r) return 0;
int len = r - l + 1;
// reindex locally: a[1..len] = p[l..r]
// dp[i] = best sum using a[1..i]
// dp[i] = max(dp[i-1], dp[i-3] + a[i])
vector<int> a(len + 1), d(len + 4, 0);
for (int i = 1; i <= len; i++)
a[i] = p[l + i - 1];
d[1] = max(0, a[1]);
if (len >= 2) d[2] = max(d[1], a[2]);
for (int i = 3; i <= len; i++)
d[i] = max(d[i - 1], d[i - 3] + a[i]);
return d[len];
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> v[i];
for (int i = 1; i <= n; i++)
p[i] = v[i] + v[i % n + 1];
// Case 1: p[1..n-2]
// Case 2: p[2..n-1]
int ans = max(solve(1, n - 2), solve(2, n - 1));
fout << ans;
return 0;
}