Pagini recente » Cod sursa (job #569796) | Cod sursa (job #3244747) | Cod sursa (job #2603558) | Cod sursa (job #252925) | Cod sursa (job #1250858)
#include <iostream>
#include <fstream>
#include <vector>
int main()
{
std::ifstream in("oo.in");
std::ofstream out("oo.out");
int n;
in >> n;
std::vector<int> v(n + 2, 0);
std::vector<int> oo(n + 2, 0);
for (int i = 0; i < n; ++i) {
in >> v[i];
}
v[n] = v[0];
in.close();
if (n == 2) {
out << v[0] + v[1] << std::endl;
out.close();
return 0;
}
if (n == 3) {
out << v[0] + v[1] + v[2] - std::min(v[0], std::min(v[1], v[2])) <<
std::endl;
out.close();
return 0;
}
// Var1. You do NOT pick the first egg.
oo[0] = 0;
oo[1] = 0;
oo[2] = 0;
oo[3] = v[1] + v[2];
for (int i = 4; i <= n; ++i) {
oo[i] = std::max(oo[i - 1], v[i - 1] + v[i - 2] + oo[i - 3]);
}
int sol1 = oo[n];
// Var2. You DO pick the first egg and the second egg.
oo[0] = 0;
oo[1] = 0;
oo[2] = v[0] + v[1];
for (int i = 3; i < n; ++i) {
oo[i] = std::max(oo[i - 1], v[i - 1] + v[i - 2] + oo[i - 3]);
}
int sol2 = oo[n - 1];
// Var 3. You DO pick the first egg and the last egg.
oo[0] = 0;
oo[1] = v[0] + v[n - 1];
for (int i = 2; i < n - 1; ++i) {
oo[i] = std::max(oo[i - 1], v[i - 1] + v[i - 2] + oo[i - 3]);
}
int sol3 = oo[n - 2];
out << std::max(std::max(sol1, sol2), sol3) << std::endl;
out.close();
return 0;
}