Pagini recente » Cod sursa (job #3350356) | Cod sursa (job #743953) | Cod sursa (job #3319486) | Cod sursa (job #1495906) | Cod sursa (job #3340291)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int solve_linear(int start, int end, const vector<int>& v) {
if (start > end) return 0;
int n = end - start + 1;
vector<int> dp(n + 1, 0);
// Ajustăm indexarea pentru a lucra local de la 1 la n
auto val = [&](int i) { return v[start + i - 2]; };
for (int i = 2; i <= n; ++i) {
int gain = val(i-1) + val(i);
int prev = (i >= 4) ? dp[i-4] : 0;
dp[i] = max(dp[i-1], gain + prev);
}
return dp[n];
}
int main() {
ifstream fin("oo.in");
ofstream fout("oo.out");
int N;
if (!(fin >> N)) return 0;
vector<int> v(N);
for (int i = 0; i < N; ++i) {
fin >> v[i];
}
if (N < 2) {
fout << 0;
return 0;
}
// Rulăm DP pe 4 variante de "tăiere" a cercului pentru a acoperi
// toate posibilitățile de excludere la capete.
int ans = 0;
// 1. Forțăm să NU se lege N cu 1 (liniar simplu)
ans = max(ans, solve_linear(0, N - 1, v));
// 2. Forțăm perechea (0, 1) -> blochează N-1 și 2
ans = max(ans, v[0] + v[1] + solve_linear(3, N - 2, v));
// 3. Forțăm perechea (N-1, 0) -> blochează N-2 și 1
ans = max(ans, v[N-1] + v[0] + solve_linear(2, N - 3, v));
// 4. Forțăm perechea (1, 2) -> blochează 0 și 3
ans = max(ans, v[1] + v[2] + solve_linear(4, N - 1, v));
fout << ans << endl;
return 0;
}