Pagini recente » Cod sursa (job #900863) | Cod sursa (job #1418202) | Cod sursa (job #1143496) | Cod sursa (job #1033833) | Cod sursa (job #1250933)
#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 + 1, 0);
std::vector<int> oo(n + 1, 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] + (i - 3 < 0 ? 0 : oo[i -
3]));
}
int sol3 = oo[n - 2];
out << std::max(std::max(sol1, sol2), sol3) << std::endl;
out.close();
return 0;
}