Pagini recente » Cod sursa (job #1869862) | Borderou de evaluare (job #1974267) | Cod sursa (job #844237) | Borderou de evaluare (job #931800) | Cod sursa (job #3340283)
#include <bits/stdc++.h>
using namespace std;
// DP pe secvența liniară
int dp_linear(const vector<int>& a) {
int n = a.size();
if (n == 0) return 0;
if (n == 1) return a[0];
if (n == 2) return a[0] + a[1];
vector<int> dp(n, 0);
// initializare pentru primele 2 sau 3 sectoare
dp[0] = 0; // nu putem alege doar primul sector singur
dp[1] = a[0] + a[1]; // alegem prima pereche
if (n >= 3) dp[2] = max(dp[1], a[1] + a[2]); // alegem perechea 2 sau prima pereche
for (int i = 3; i < n; i++) {
// dp[i-1] -> nu alegem perechea (i-1,i)
// dp[i-3] + a[i-1]+a[i] -> alegem perechea (i-1,i)
dp[i] = max(dp[i-1], dp[i-3] + a[i-1] + a[i]);
}
return dp[n-1];
}
int max_oua(const vector<int>& a) {
int N = a.size();
if (N == 2) return a[0] + a[1];
// Caz 1: ignorăm perechea care include sectorul 1 -> folosim sectoarele 2..N
vector<int> a1(a.begin() + 1, a.end()); // 2..N
int case1 = dp_linear(a1);
// Caz 2: ignorăm perechea care include sectorul N -> folosim sectoarele 1..N-1
vector<int> a2(a.begin(), a.end() - 1); // 1..N-1
int case2 = dp_linear(a2);
return max(case1, case2);
}
int main() {
// citire si scriere fisier
freopen("oo.in", "r", stdin);
freopen("oo.out", "w", stdout);
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++) cin >> a[i];
int rezultat = max_oua(a);
cout << rezultat << "\n";
return 0;
}