Разбор задачи «Городские пропуска»

В задаче даны дни, в которые нужно совершить поездки, и стоимости трёх видов пропусков:

• на 1 день;
• на 7 дней;
• на 30 дней.

Нужно покрыть все нужные дни поездок с минимальной суммарной стоимостью.

1. Наблюдение

В каждый нужный день мы должны принять одно из трёх решений:

• купить пропуск на 1 день;
• купить пропуск на 7 дней;
• купить пропуск на 30 дней.

Если мы уже стоим в некотором дне поездки days[i], то после покупки пропуска часть следующих дней тоже автоматически покрывается.

Значит, задача естественно разбивается на подзадачи:

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

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

2. Формулировка динамики

Обозначим:

• days[i] — i-й день, в который нужна поездка;
• dp[i] — минимальная стоимость покрыть все поездки, начиная с индекса i.

Тогда ответом будет dp[0].

База

Если все дни уже покрыты, то платить больше не нужно:

• dp[n] = 0, где n — количество дней поездок.

Переход

Пусть мы находимся в позиции i.

Вариант 1. Купить пропуск на 1 день

Он покрывает только день days[i].

Тогда нужно найти первый индекс j1, для которого день уже не покрыт, то есть первый индекс после текущего дня.

Стоимость:

• cost1 + dp[j1]

Вариант 2. Купить пропуск на 7 дней

Он покрывает все дни от days[i] до days[i] + 6.

Нужно найти первый индекс j7, для которого:

• days[j7] >= days[i] + 7

Стоимость:

• cost7 + dp[j7]

Вариант 3. Купить пропуск на 30 дней

Он покрывает все дни от days[i] до days[i] + 29.

Нужно найти первый индекс j30, для которого:

• days[j30] >= days[i] + 30

Стоимость:

• cost30 + dp[j30]

Тогда:

dp[i] = min(cost1 + dp[j1], cost7 + dp[j7], cost30 + dp[j30])

3. Почему здесь удобно использовать бинарный поиск

Массив days уже отсортирован по возрастанию.

Значит, индексы j1, j7, j30 можно искать бинарным поиском:

• первый индекс, где days[pos] >= days[i] + 1
• первый индекс, где days[pos] >= days[i] + 7
• первый индекс, где days[pos] >= days[i] + 30

Это стандартный lower_bound в C++ и bisect_left в Python.

Так мы получаем аккуратное решение за O(n log n).

При ограничении n <= 365 оно работает очень быстро.

4. Порядок вычисления

Так как dp[i] зависит только от значений с большими индексами, удобно считать динамику справа налево:

• сначала dp[n] = 0;
• затем dp[n-1], dp[n-2], ... , dp[0].

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

Пусть:

• days = [1, 4, 6, 7, 8, 20]
• costs = [2, 7, 15]

Рассмотрим день 4.

Если купить:

• билет на 1 день, мы заплатим 2, и дальше останутся дни с 6;
• билет на 7 дней, он покроет 4, 6, 7, 8, и дальше останется только 20;
• билет на 30 дней, он покроет вообще все оставшиеся дни, но стоит 15.

На каждом шаге мы выбираем самый выгодный вариант.

Итоговый ответ для этого примера — 11.

6. Альтернативная идея

Можно решать задачу и по дням календаря от 1 до 365, отмечая, нужен ли проезд в этот день. Тогда динамика строится по номеру дня.

Но решение по индексам массива days обычно удобнее:

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

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

Ошибка 1. Неправильно понимать длину действия пропуска

Если билет куплен в день d, то:

• на 7 дней он покрывает от d до d+6;
• на 30 дней он покрывает от d до d+29.

Поэтому следующий не покрытый день ищется как:

• days[i] + 7
• days[i] + 30

а не +6 и +29.

Ошибка 2. Делать переход по соседнему индексу вручную

Нельзя считать, что после 7-дневного билета мы просто переходим в i+7. В массиве days находятся только нужные дни поездок, а не все дни подряд.

Ошибка 3. Пытаться жадно выбирать самый дешёвый билет в текущий момент

Локально дешёвый билет не всегда даёт глобально лучший ответ. Поэтому здесь нужна именно динамика.

8. Оценка сложности

Пусть n — число дней поездок.

Для каждой позиции мы делаем 3 бинарных поиска.

Время

• O(n log n)

Память

• O(n)

При данных ограничениях это решение легко проходит.

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<int> days(n);
    for (int i = 0; i < n; i++) {
        cin >> days[i];
    }

    vector<int> costs(3);
    for (int i = 0; i < 3; i++) {
        cin >> costs[i];
    }

    vector<int> dp(n + 1, 0);

    for (int i = n - 1; i >= 0; i--) {
        int j1 = lower_bound(days.begin(), days.end(), days[i] + 1) - days.begin();
        int j7 = lower_bound(days.begin(), days.end(), days[i] + 7) - days.begin();
        int j30 = lower_bound(days.begin(), days.end(), days[i] + 30) - days.begin();

        dp[i] = min({
            costs[0] + dp[j1],
            costs[1] + dp[j7],
            costs[2] + dp[j30]
        });
    }

    cout << dp[0] << '\n';
    return 0;
}

10. Пояснение к коду на C++

dp[n] = 0

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

Цикл справа налево

for (int i = n - 1; i >= 0; i--)

Мы считаем ответы для всё более ранних позиций.

Поиск первого непокрытого дня

int j7 = lower_bound(days.begin(), days.end(), days[i] + 7) - days.begin();

Это индекс первого дня, который уже не покрывается 7-дневным пропуском.

Переход

dp[i] = min({
    costs[0] + dp[j1],
    costs[1] + dp[j7],
    costs[2] + dp[j30]
});

Пробуем все три вида билетов и берём минимум.

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

from bisect import bisect_left

n = int(input())
days = list(map(int, input().split()))
costs = list(map(int, input().split()))

dp = [0] * (n + 1)

for i in range(n - 1, -1, -1):
    j1 = bisect_left(days, days[i] + 1)
    j7 = bisect_left(days, days[i] + 7)
    j30 = bisect_left(days, days[i] + 30)

    dp[i] = min(
        costs[0] + dp[j1],
        costs[1] + dp[j7],
        costs[2] + dp[j30]
    )

print(dp[0])

12. Пояснение к коду на Python

В Python используется функция:

bisect_left(days, x)

Она возвращает первую позицию, куда можно вставить x, чтобы порядок не нарушился.

То есть это и есть индекс первого элемента:

• не меньшего x.

Поэтому:

• bisect_left(days, days[i] + 7)

даёт индекс первого дня, который уже не покрывается 7-дневным билетом.

13. Почему решение корректно

Докажем идею кратко.

Рассмотрим оптимальное решение для подзадачи, начинающейся с индекса i.

Первый билет в этом решении обязательно один из трёх типов:

• на 1 день;
• на 7 дней;
• на 30 дней.

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

Именно эту стоимость мы и обозначили как dp[j].

Значит, оптимальный ответ для dp[i] действительно равен минимуму из трёх вариантов перехода.

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

14. Итог

Это хорошая задача на динамическое программирование по массиву состояний.

Ключевая идея:

• перейти от «по каким дням покупать билеты» к формулировке «какова минимальная стоимость покрыть поездки, начиная с позиции i».

После этого решение становится прямолинейным:

• динамика справа налево;
• для каждого состояния три перехода;
• следующий индекс ищется бинарным поиском.

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