Pagini recente » Cod sursa (job #3341560) | Cod sursa (job #3330015) | Monitorul de evaluare | Cod sursa (job #1803852) | Cod sursa (job #3340297)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n, v[100005], dp[100005];
// Calculeaza maximul pe un sir liniar
int solve_linear(int start, int end)
{
if (start > end) return 0;
int len = end - start + 1;
if (len < 2) return 0;
// Resetare dp pentru segmentul curent
for (int i = 0; i <= len; i++) dp[i] = 0;
// dp[i] = profitul maxim folosind primele i elemente din segment
for (int i = 2; i <= len; i++)
{
dp[i] = dp[i - 1]; // Nu luam pereche la i
int val_pereche = v[start + i - 2] + v[start + i - 1];
int anterior = (i >= 4) ? dp[i - 4] : 0;
if (val_pereche + anterior > dp[i])
{
dp[i] = val_pereche + anterior;
}
}
return dp[len];
}
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;
}
int sol = 0;
// Cazul 1: NU folosim perechea (v[n-1], v[0])
// Rezolvam pur si simplu liniar
sol = max(sol, solve_linear(0, n - 1));
// Cazul 2: FORȚĂM perechea (v[n-1], v[0])
// Aceasta blocheaza v[n-2] si v[1].
// Ramane de calculat optimul pe segmentul [2, n-3]
if (n >= 4)
{
sol = max(sol, v[n - 1] + v[0] + solve_linear(2, n - 3));
}
// Cazul 3: FORȚĂM perechea (v[0], v[1])
// Aceasta blocheaza v[n-1] si v[2].
// Ramane de calculat optimul pe segmentul [3, n-2]
if (n >= 4)
{
sol = max(sol, v[0] + v[1] + solve_linear(3, n - 2));
}
// Cazul 4: FORȚĂM perechea (v[1], v[2])
// Aceasta blocheaza v[0] si v[3].
// Ramane de calculat optimul pe segmentul [4, n-1]
if (n >= 5)
{
sol = max(sol, v[1] + v[2] + solve_linear(4, n - 1));
}
fout << sol << endl;
return 0;
}