Посчитать число последовательностей длины N (N <= 1000) элементы которой из [1..K] (K <= 200) таких, что не существует i < j < k и A[i] > A[j] > A[k].
Очевидно, существует простое решение за N*K^3, если в состоянии запоминать два максимальных элемента, что, естественно, не проходит по времени.
Спасибо!
Динамика dp[n][x][y] — количество последовательностей, где осталось поставить n элементов, максимальный из поставленных равен x и нельзя ставить элементы меньше y. Переход за O(k) можно превратить в O(1) с помощью частичных сумм.
Спасибо, AC.