Блог пользователя feruz.atamuradov

Автор feruz.atamuradov, история, 8 лет назад, По-русски
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Хоть бы "пожалуйста" сказал

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Эта ДП, строится так.

// Ts, Te <= 30000
int dp[30002]; // dp[i] - это максимум количество сменарий которые можно участвовать, до i-той минуты.
int e[30002]; //  e[i] - это максимальная начальная время из всех сменарий которые Ts == i.

//  e[i] = 0, i = 0..30002  initialization.
//  for i = 0..n-1    e[ te ] = max(e[te], ts); // ts, te - начальная и конечная время сменарий.

//  dp[0] = 0.

//  i = 1..30002  :   
//     1. dp[i] = dp[i-1] ; // i - той минуты никакой сменарий нет, тогда dp[i] - равен предыдушее.
//     2.    вот здесь может закончились какое нибуд сменарий в i-той минут, нам нужен такой сменарий, который  начался позднее из всех ,  т.е. e[i] - Это начальная время интересующиее нам сменарий.
  Поэтому,  если  e[i] > 0  ( это означает действительно есть хотя бы один сменарий), тогда
       dp[i] = max(dp[i],  1 + dp[ e[i] - 1] ).


Ну конечно, dp[30001] - Ответь ).
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

В этой задаче работает жадность. Давайте отсортим пары (Te, Ts). Теперь покажем, что можно брать элементы в порядке этой сортировки, если Tsi > Tej, где j — последний взятый элемент, а i — текущий просматриваемый. Изначально возьмем первую пару, понятно что так как она заканчивается раньше всех, то не имеет смысла брать никакую другую пару. Теперь уберем все пары, что начинаются раньше, чем заканчивается первая и получим задачу меньше исходной, для которой можно сделать аналогичные рассуждения.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем feruz.atamuradov (предыдущая версия, новая версия, сравнить).