1. Идея

В каждый день нужно выбрать одно из трёх занятий, но нельзя выбирать одно и то же занятие два дня подряд.

Это очень похоже на задачу динамического программирования по дням: для каждого дня будем хранить лучший ответ, если в этот день выбрано:

• первое занятие,
• второе занятие,
• третье занятие.

Тогда переходы легко выписываются: если сегодня выбрали, например, первое занятие, то вчера можно было выбрать только второе или третье.

2. Наблюдения

Обозначим:

• dp0 — максимальное удовольствие после текущего дня, если в текущий день выбрано первое занятие;
• dp1 — то же самое для второго занятия;
• dp2 — то же самое для третьего занятия.

Для первого дня всё просто:

• dp0 = a1
• dp1 = b1
• dp2 = c1

Дальше, если на очередной день даны значения a, b, c, то:

• новое dp0 = a + max(dp1, dp2)
• новое dp1 = b + max(dp0, dp2)
• новое dp2 = c + max(dp0, dp1)

Почему именно так:

• если сегодня выбрано первое занятие, вчера нельзя было выбирать первое;
• значит, лучший вариант — взять максимум из состояний, где вчера было второе или третье занятие.

В конце ответом будет максимум из трёх состояний, потому что последний день может заканчиваться любым занятием.

3. Алгоритм

1. Считать n.
2. Считать значения для первого дня: a, b, c.
3. Инициализировать:
   • dp0 = a
   • dp1 = b
   • dp2 = c
4. Для каждого следующего дня:
   • считать a, b, c;
   • вычислить:
     • ndp0 = a + max(dp1, dp2)
     • ndp1 = b + max(dp0, dp2)
     • ndp2 = c + max(dp0, dp1)
   • присвоить:
     • dp0 = ndp0
     • dp1 = ndp1
     • dp2 = ndp2
5. Вывести max(dp0, dp1, dp2).

4. Почему это работает

Докажем корректность идеи.

Рассмотрим некоторый день i.

Пусть dp0 для этого дня — это максимальное суммарное удовольствие за первые i дней, если в день i выбрано первое занятие. Аналогично определяются dp1 и dp2.

Теперь посмотрим, как получить значение для первого занятия в день i.

Если в день i выбрано первое занятие, то в день i - 1 нельзя было выбирать первое занятие. Значит, в день i - 1 было выбрано либо второе, либо третье. Среди всех таких допустимых планов нужно взять тот, который даёт максимальную сумму. Поэтому:

• лучший вариант для первого занятия в день i равен удовольствию a_i за этот день плюс максимум из лучших планов, заканчивавшихся вторым или третьим занятием в день i - 1.

То есть:

• dp0(i) = a_i + max(dp1(i - 1), dp2(i - 1))

Точно так же:

• dp1(i) = b_i + max(dp0(i - 1), dp2(i - 1))
• dp2(i) = c_i + max(dp0(i - 1), dp1(i - 1))

База для первого дня верна очевидно: если день только один, то максимальная сумма при выборе каждого занятия просто равна удовольствию от этого занятия.

Значит, по индукции все значения вычисляются правильно, а итоговый ответ — максимум среди трёх вариантов в последний день.

5. Сложность

На каждом дне выполняется константное число операций.

• Время: O(n)
• Память: O(1)

Память O(1) получается потому, что нам нужны только значения для предыдущего дня, а не весь массив динамики.

6. Код на C++17

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long a, b, c;
    cin >> a >> b >> c;

    long long dp0 = a, dp1 = b, dp2 = c;

    for (int i = 2; i <= n; i++) {
        cin >> a >> b >> c;
        long long ndp0 = a + max(dp1, dp2);
        long long ndp1 = b + max(dp0, dp2);
        long long ndp2 = c + max(dp0, dp1);
        dp0 = ndp0;
        dp1 = ndp1;
        dp2 = ndp2;
    }

    cout << max(dp0, max(dp1, dp2)) << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a, b, c = map(int, input().split())

dp0 = a
dp1 = b
dp2 = c

for _ in range(1, n):
    a, b, c = map(int, input().split())
    ndp0 = a + max(dp1, dp2)
    ndp1 = b + max(dp0, dp2)
    ndp2 = c + max(dp0, dp1)
    dp0, dp1, dp2 = ndp0, ndp1, ndp2

print(max(dp0, dp1, dp2))