Pagini recente » Cod sursa (job #3328937) | Cod sursa (job #3304115) | Cod sursa (job #3349130) | Cod sursa (job #3322847) | Cod sursa (job #3340292)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
// Funcție care calculează maximul pe un șir liniar
// dp[i] = maximul folosind elementele de la 0 la i
long long solve_linear(const vector<int>& a) {
int n = a.size();
if (n < 2) return 0;
vector<long long> dp(n, 0);
for (int i = 1; i < n; i++) {
// Opțiunea 1: Nu luăm o pereche care se termină la i
dp[i] = dp[i - 1];
// Opțiunea 2: Luăm perechea (i-1, i)
long long current_pair = a[i] + a[i - 1];
if (i >= 3) {
dp[i] = max(dp[i], current_pair + dp[i - 3]);
} else {
dp[i] = max(dp[i], current_pair);
}
}
return dp[n - 1];
}
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 << v[0] + v[1] << endl;
return 0;
}
long long max_oua = 0;
// Cazul 1: NU folosim legătura dintre ultimul și primul (v[n-1] + v[0])
// Rezolvăm liniar normal: 0, 1, 2, ..., n-1
max_oua = max(max_oua, solve_linear(v));
// Cazul 2: Forțăm perechea (v[n-1], v[0])
// Asta blochează v[n-2] și v[1].
// Rămâne de calculat optimul pentru segmentul [2, n-3]
vector<int> c2;
for (int i = 2; i <= n - 3; i++) c2.push_back(v[i]);
max_oua = max(max_oua, (long long)v[n - 1] + v[0] + solve_linear(c2));
// Cazul 3: Forțăm perechea (v[0], v[1])
// Asta blochează v[n-1] și v[2].
// Rămâne de calculat optimul pentru segmentul [3, n-2]
vector<int> c3;
for (int i = 3; i <= n - 2; i++) c3.push_back(v[i]);
max_oua = max(max_oua, (long long)v[0] + v[1] + solve_linear(c3));
fout << max_oua << endl;
return 0;
}