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

Автор NotImplemented, 11 лет назад, По-русски

Timus 1696

Посчитать число последовательностей длины N (N <= 1000) элементы которой из [1..K] (K <= 200) таких, что не существует i < j < k и A[i] > A[j] > A[k].

Очевидно, существует простое решение за N*K^3, если в состоянии запоминать два максимальных элемента, что, естественно, не проходит по времени.

Спасибо!

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

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

Динамика dp[n][x][y] — количество последовательностей, где осталось поставить n элементов, максимальный из поставленных равен x и нельзя ставить элементы меньше y. Переход за O(k) можно превратить в O(1) с помощью частичных сумм.