Решение через динамическое программирование. F(k) - лучшая сумма, которую можно набрать из карточек, начиная с k, когда можно один раз взять 2 карточки, g(k) - тоже самое, но 2 карточки брать уже нельзя.
g(k) = max(a[k]+g(k+2),g(k+1)); - или вы берете первую карточку, то робот берет следующую и далее задача повторяется. Второй вариант - вы пропускаете эту карточку, тогда ее берет робот. Задача повторяется со следующей карточки.
f(k) = max(a[k]+a[k+1]+g(k+3), a[k] + f(k+2), f(k+1));
- так же, мы либо берем 2 карточки, либо 1, либо 0. Если мы берем 2, то в будущем 2 уже брать нельзя, придется брать g(k+3).
Вот решение на C++ (вместо 2 функций используется флаг, можно ли брать 2 карточки)
vector<int> dp[2]; // заполнен MIN_INT, размером с n.
vector<int> take[2]; // размером с n.
int f(const vector<int> &a, int k, int can_take_two) {
if(k >= n) return 0;
if (dp[k][can_take_two] > MIN_INT) return dp[k][can_take_two];
// skip;
int best = f(a, k+1, can_take_two);
take[k][can_take_two] = 0;
// take 1;
int cur = f(a, k+2, can_take_two) + a[k];
if (cur > best) {
best = cur;
take[k][can_take_two] = 1;
}
if (can_take_two && k + 1 < n) {
cur = f(k+3, 0) + a[k] + a[k+1];
if (cur > best) {
best = cur;
take[k][can_take_two] = 2;
}
}
dp[k][can_take_two] = best;
return best;
}
//...
// f(a, 0, 1) - вернет лучшую сумму.
//Для восстановления ответа можно воспользоваться массивом take, который хранит для каждого состояния, сколько карточек брать:
k = 0; ct = 1;
while (k <n) {
num = take[k][ct];
for (j = 0; j < num; ++j) {
cout << a[k+j] << " ";
}
if (num == 2) ct = 0;
k += num + 1;
}
Если нужна только сумма, а не сам набор чисел, то можно развернуть рекурсию в 2 вложенных цикла (один от n до 0, другой от 0 до 1) и хранить только 3 последних строчки массива dp.
Средний
Простой
