Разбор задачи «Ярмарочные стойки»

Идея задачи

У нас есть две строки чисел длины n:

• a[i] — прибыль верхней стойки в столбце i,
• b[i] — прибыль нижней стойки в столбце i.

Нужно выбрать несколько стоек так, чтобы:

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

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

Как посмотреть на задачу правильно

Будем обрабатывать столбцы слева направо.

Для каждого столбца нам важно понимать не только максимальную сумму на префиксе, но и чем именно закончился оптимальный выбор:

• верхней стойкой,
• нижней стойкой,
• или мы вообще ничего не взяли в текущем столбце.

Это подсказывает динамику по состояниям.

Динамика

Обозначим:

• dp0[i] — максимальная прибыль на первых i столбцах, если в столбце i мы ничего не берём;
• dp1[i] — максимальная прибыль на первых i столбцах, если в столбце i мы берём верхнюю стойку;
• dp2[i] — максимальная прибыль на первых i столбцах, если в столбце i мы берём нижнюю стойку.

Будем считать столбцы с 1 до n.

Переходы

1. Не брать ничего в столбце i

Тогда до этого в столбце i - 1 могло быть что угодно:

 dp0[i] = max(dp0[i - 1], dp1[i - 1], dp2[i - 1])

2. Взять верхнюю стойку в столбце i

Тогда в предыдущем столбце нельзя было брать верхнюю стойку, иначе нарушится условие. Значит перед этим допустимы только состояния:

• dp0[i - 1] — в предыдущем столбце ничего не взяли,
• dp2[i - 1] — в предыдущем столбце взяли нижнюю стойку.

Поэтому:

 dp1[i] = max(dp0[i - 1], dp2[i - 1]) + a[i]

3. Взять нижнюю стойку в столбце i

Аналогично:

 dp2[i] = max(dp0[i - 1], dp1[i - 1]) + b[i]

Ответ

После обработки всех столбцов ответ равен:

 max(dp0[n], dp1[n], dp2[n])

Почему этого достаточно

Потому что ограничение касается только соседних столбцов.

Чтобы корректно продолжить построение ответа в столбце i, нам нужно знать лишь то, что произошло в столбце i - 1:

• взяли верхнюю,
• взяли нижнюю,
• ничего не взяли.

Более старая история уже не важна. Именно это и делает динамику корректной.

Пример работы

Пусть:

n = 3
a = [1, 100, 3]
b = [50, 2, 50]

Посчитаем по столбцам.

Столбец 1

 dp0 = 0
 dp1 = 1
 dp2 = 50

Столбец 2

 new_dp0 = max(0, 1, 50) = 50
 new_dp1 = max(0, 50) + 100 = 150
 new_dp2 = max(0, 1) + 2 = 3

Столбец 3

 new_dp0 = max(50, 150, 3) = 150
 new_dp1 = max(50, 3) + 3 = 53
 new_dp2 = max(50, 150) + 50 = 200

Ответ:

max(150, 53, 200) = 200

Оптимальный выбор:

• нижняя в столбце 1,
• верхняя в столбце 2,
• нижняя в столбце 3.

Сумма равна 50 + 100 + 50 = 200.

Оптимизация памяти

Заметим, что значения для столбца i зависят только от значений для столбца i - 1.

Значит хранить весь массив dp не нужно. Достаточно трёх переменных:

• dp0 — ничего не взяли в текущем столбце,
• dp1 — взяли верхнюю,
• dp2 — взяли нижнюю.

На каждом шаге считаем новые значения и перезаписываем старые.

Это даёт:

• время O(n),
• память O(1).

Типичные ошибки

Ошибка 1. Пытаться жадно брать максимум в каждом столбце

Например, брать в столбце просто более выгодную из двух стоек. Это неверно, потому что локально выгодный выбор может испортить более выгодную цепочку дальше.

Ошибка 2. Считать, что из двух соседних столбцов нельзя брать обе стойки

Это не так. Брать можно, если они находятся в разных строках.

Например:

• верхняя в столбце i,
• нижняя в столбце i + 1

— это допустимо.

Ошибка 3. Использовать тип int

Прибыль каждой стойки может быть до 10^9, а столбцов до 10^5. Сумма может быть очень большой, поэтому нужен тип:

• long long в C++,
• обычный int в Python подходит, потому что он длинный.

Эталонное решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    long long dp0 = 0;
    long long dp1 = 0;
    long long dp2 = 0;

    for (int i = 1; i <= n; i++) {
        long long new_dp0 = max({dp0, dp1, dp2});
        long long new_dp1 = max(dp0, dp2) + a[i];
        long long new_dp2 = max(dp0, dp1) + b[i];

        dp0 = new_dp0;
        dp1 = new_dp1;
        dp2 = new_dp2;
    }

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

Эталонное решение на Python

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

dp0 = 0
dp1 = 0
dp2 = 0

for i in range(1, n + 1):
    new_dp0 = max(dp0, dp1, dp2)
    new_dp1 = max(dp0, dp2) + a[i]
    new_dp2 = max(dp0, dp1) + b[i]

    dp0 = new_dp0
    dp1 = new_dp1
    dp2 = new_dp2

print(max(dp0, dp1, dp2))

Почему код корректен

Докажем это по индукции по номеру столбца.

База

До обработки первого столбца:

• прибыль равна 0,
• мы ничего не выбрали.

Это корректное начальное состояние.

Переход

Предположим, что после обработки первых i - 1 столбцов значения dp0, dp1, dp2 действительно равны максимумам для своих состояний.

Тогда для столбца i:

• new_dp0 — лучший вариант, если мы в этом столбце ничего не берём. Значит можно взять максимум из всех трёх состояний предыдущего столбца.
• new_dp1 — лучший вариант, если берём верхнюю стойку. Предыдущий столбец не мог закончиться верхней стойкой, поэтому допустимы только dp0 и dp2.
• new_dp2 — аналогично, допустимы только dp0 и dp1.

Значит все переходы корректны, и новые состояния тоже корректны.

По индукции алгоритм верно вычисляет ответ.

Сложность

По времени

Мы один раз проходим по всем столбцам и делаем в каждом константное число операций:

O(n)

По памяти

Используем только несколько переменных:

O(1)

Вывод

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

Ключевая мысль такая:

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

Итог: простая и очень эффективная динамика за O(n).