Pagini recente » Cod sursa (job #3338754) | Cod sursa (job #3348252) | Cod sursa (job #3313237) | Cod sursa (job #3355573) | Cod sursa (job #3340295)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n;
int v[100005];
int dp[100005];
// Calculeaza maximul pe un sir liniar de lungime 'len'
// folosind elementele din tabloul 'a'
int solve_linear(int a[], int len) {
if (len < 2) return 0;
// Initializam dp
for (int i = 0; i <= len; i++) dp[i] = 0;
// dp[i] = maximul folosind primele i elemente
// O pereche (i-1, i) poate fi adunata daca precedenta
// s-a terminat la i-4 (lasand i-2 si i-3 libere)
for (int i = 2; i <= len; i++) {
dp[i] = dp[i-1]; // Nu luam pereche la pozitia i
int current_pair = a[i-1] + a[i-2];
int prev_val = (i >= 4) ? dp[i-4] : 0;
if (current_pair + prev_val > dp[i]) {
dp[i] = current_pair + prev_val;
}
}
return dp[len];
}
int temp[100005];
int main() {
ifstream fin("oo.in");
ofstream fout("oo.out");
if (!(fin >> n)) return 0;
for (int i = 0; i < n; i++) fin >> v[i];
if (n == 2) {
fout << v[0] + v[1] << endl;
return 0;
}
// --- CAZUL 1: NU luam perechea (v[n-1], v[0]) ---
// Rezolvam liniar pur si simplu de la 0 la n-1
int rez1 = solve_linear(v, n);
// --- CAZUL 2: LUAM perechea (v[n-1], v[0]) ---
// Asta blocheaza v[1] si v[n-2].
// Trebuie sa rezolvam restul elementelor: v[2], v[3], ..., v[n-3]
int rez2 = 0;
if (n >= 4) {
int m = 0;
for (int i = 2; i <= n - 3; i++) {
temp[m++] = v[i];
}
rez2 = v[n-1] + v[0] + solve_linear(temp, m);
} else {
rez2 = v[n-1] + v[0];
}
fout << max(rez1, rez2) << endl;
return 0;
}