Pagini recente » Cod sursa (job #2277379) | Cod sursa (job #1263405) | Cod sursa (job #527447) | Cod sursa (job #1555057) | Cod sursa (job #3281931)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int solve_linear(const vector<int> &a, int start, int end)
{
int n = end - start + 1; // numărul de elemente din subsecvență
// dp[i] va reprezenta maximul de ouă colectate din subsecvența care începe la poziția i (reindexată de la start)
// Alocăm câteva poziții extra pentru a evita verificări de frontieră
vector<int> dp(n + 4, 0);
// Cazurile de bază:
// Dacă avem doar 1 element, nu putem forma o pereche.
dp[n] = 0;
if (n >= 2)
dp[n - 1] = a[start + n - 2] + a[start + n - 1];
// Calculăm dp de la i = n-2 până la 1
for (int i = n - 2; i >= 1; i--)
{
int pairVal = a[start + i - 1] + a[start + i]; // alegem perechea (i, i+1)
dp[i] = max(dp[i + 1], pairVal + dp[i + 3]);
}
return dp[1];
}
int main()
{
ifstream fin("oo.in");
ofstream fout("oo.out");
int N;
fin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++)
{
fin >> a[i];
}
if (N == 2)
{
fout << a[0] + a[1] << "\n";
return 0;
}
// Deoarece vectorul a este 0-indexat, iar în solve_linear considerăm startul ca 1-indexat:
// Pentru subproblema A: folosim sectoarele 1..(N-1) -> echivalează cu indexii 0..(N-2)
int solA = solve_linear(a, 0, N - 2);
// Pentru subproblema B: folosim sectoarele 2..N -> echivalează cu indexii 1..(N-1)
int solB = solve_linear(a, 1, N - 1);
int solC = solve_linear(a, 2, N);
fout << max(solC, max(solA, solB)) << "\n";
return 0;
}