Блог пользователя RAD

Codeforces Beta Round #28 (Разбор задачи D)
Автор RAD, 14 лет назад, По-русски

Разделим все грузовики на классы по сумме l + r + c. Утверждается, что все входящие в ответ грузовики находятся в одном классе.

Для каждого класса решим задачу отдельно. Будем рассматривать все грузовики из одного класса в том порядке, в котором они едут, и поддерживать такую динамику: z[k] = наибольшая сумма, которую можно набрать, если у последнего взятого грузовика ri = k. Рассмотрим грузовик номер i - возможны 2 перехода:

Он может улучшить z[ri] значением z[ri + ci] + vi, т. е. продолжить уже начатую колонну машин, в которой r у последнего грузовика равно ri + ci. (Для соседних в колонне грузовиков должно выполняться: rprev  =  ri  +  ci )

Если li = 0, он может улучшить z[ri] значением vi, т. е. стать первым в новой колонне машин. (Для первого в колонне грузовика должно выполняться: li = 0)

Ответ на задачу будет записан в z[0].

Для восстановления вошедших в ответ грузовиков, вместе с наибольшей суммой в z можно хранить номер последнего грузовика, улучшившего эту сумму. Еще мы отдельно храним предка p для каждого грузовика, улучшившего хоть что-то в z. Этот предок считается один раз когда мы рассматриваем i-ый грузовик и больше не изменяется: p[i] = -1 если грузовик i стал новым началом колонны, иначе p[i] = последний грузовик, улучшивший z[ri + ci].

Начинать восстановление ответа нужно с последнего грузовика, улучшившего z[0]. Дальше все восстанавливается только по p.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Не могли бы вы поподробнее описать процесс восстановления ответа? Пусть у нас есть такой тест:

3

1 1 0 1

1 1 1 0

2 1 0 1

Значение ответа получится верное - 2. Но при восстановлении, когда мы придем в z[1], там будет записано 2 и что мы пришли туда по 3-му грузовику, т. е. окончательный ответ получится

2

3 2

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

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    При восстановлении ответа мы не используем z. Мы отдельно храним предка для каждого грузовика, улучшившего хоть что-то в z. Этот предок считается один раз когда мы рассматриваем i-ый грузовик.
    В вашем тесте:
    Для грузовика 1: помечаем что он первый в колонне (p[1] = -1), в z[1] кладем сумма=1 и последний грузовик=1
    Для грузовика 2: улучшается z[0]. Посмотрим в z[1], там последний грузовик=1, значит p[2]=1, в z[0] сумма=2, последний грузовик=2
    Для грузовика 3: помечаем что он первый в колонне (p[3] = -1), улучшаем z[1]: сумма=2, последний грузовик=3
    Начинать восстановление ответа нужно с последнего грузовика из z[0], т. е. 2.
    Дальше все восстанавливается только по p. Т. е. из 2 мы придем в 1.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо большое, удалось сдать. Мне кажется, что это стоит добавить в разбор.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
During the competition I misunderstood the problem statement. I thought that each truck wants AT LEAST l/r people to go before/after this truck. The reason was the first paragraph where it was said that some people do not want to be first and some do not want do be the last ones. It took me more than 20 minutes to discover my mistake (because my program gave different answer on the first example test). I know that I should have checked sample tests carefuly before coding, but in my opinion adding a word "exactly" in the problem statement would help.

PS The task with "at least" is also solvable with the same limits on input data.
→ Ответить