Как решить этот вопрос, заданный в конкурсе премиум-кода?

Question

Может ли кто-нибудь подсказать мне, как решить этот вопрос программирования? Это похоже на проблему DP, на которую я не смог найти ответ.

Вопрос:

Есть реклама 'n'. Каждое объявление имеет значение эффективности, связанное с ним, которое задается в массиве размером «n» в формате [v1, v2,…, vn], где «v1» - это значение эффективности первого объявления, «v2» - этозначение эффективности второго объявления и т. д. Показ, на котором будут показываться эти объявления, имеет длину 'm' (начиная с 0 до m), а время показа рекламы указывается в формате [(a1, b1), (a2, b2),…, (An, bn)], где i-й кортеж в массиве обозначает время i-го объявления в формате (start_time, end_time). Обратите внимание, что любые «ai» и «bi» не могут быть меньше 0 и не могут быть больше «m». Когда вы решите показать объявление, вы не сможете показать другое объявление в течение 4 минут после его окончания. Таким образом, если вы выбрали показ объявлений с временными интервалами (2, 4), то вы не сможете показывать другое объявление до 9, поэтому следующим объявлением не может быть (8, 10), но это может быть (9, 12). Вы должны выбрать объявления для показа аудитории таким образом, чтобы максимально увеличить сумму значений эффективности объявлений с учетом вышеуказанных ограничений. Например, если «m» равно 20, а время показа объявлений составляет [(2, 3), (6, 9), (10, 12), (12, 13), (14, 17)] иЗначения эффективности - [3, 9, 10, 6, 7], тогда вы можете показывать объявления 2 и 5 (индексация по одному) и иметь значение эффективности 16, что является максимумом, который вы можете получить с учетом ограничений.

Answer 1

Ваша проблема может быть сведена к следующему, давайте рассмотрим 1d сегменты, которые можно описать как (start_i, end_i, value_i).

Пусть S = массив доступных 1d сегментов

Чтомы хотим найти непересекающиеся сегменты, которые суммируются с максимально возможным значением и помещаются в интервале [0, м] (показать длину)

Пусть DP [x] = наилучшее достижимое значение для покрытия сегмента[0, x] с подмножеством доступных 1d сегментов.

Отношение рекуррентности таково: для элемента (s_i, e_i, v_i) мы можем выбрать его или нет.

DP [e_i] = DP [e_i - 1]

DP [e_i] = максимум (DP [e_i], DP [s_i - 1] + v_i)

dp[0] = 0;
// sort the events by increasing e_i, because
// we want to process first the events that finish earlier

for( int END = 1; END <= m; ++END)
{
    dp[end] = dp[end - 1];
    for( each ELEMENT(s_i, e_i, v_u) with (e_i == END) )
    {
        dp[end] = max( dp[end], dp[s_i - 1] + v_i ) 
    }
}