Лексикографически наименьшая последовательность с числом инверсий

Не совсем понимаю, зачем такое маленькое ограничение на количество чисел. Из N чисел можно составить последовательность с любым количеством инверсий от 0 до N*(N-1)/2. Следовательно, можно подбирать искомую последовательность по одному числу: поставим единицу в начало, тогда остается последовательность из N-1 числа и она должна содержать К инверсий. Если К не превышает (N-1)*(N-2)/2, то оставляем единицу, иначе ставим в начало двойку и теперь оставшаяся последовательность должна содержать K-1 инверсию (единица с двойкой находятся в обратном порядке) и т.д.. Аналогично подбираем все числа.

Часто в задачах где нужно найти К-й лекс. набор, мин. лекс набор, удовлетворяющий условиям или что-то подобное используется динамика (в данном случае из первой части), а затем зная количество наборов, удовлетворяющих заданному условию подбирается сам искомый набор по одному элементу. В данном случае вторую часть можно было решать иначе, правда тоже подбором элементов с начала.

Будем так же строить последовательность с начала. Поставим единицу на первую позицию. Если dp(i-1,K)>0, то можем оставлять единицу там же и переходить ко второй позиции, если же dp(i-1,K)==0, то поставим двойку на первую позицию. Двойка образовывает инверсию с единицей, которая будет стоять после нее, поэтому теперь нужно требовать чтобы dp(i-1,K-1) было положительным. Далее, если dp(i-1,K-1)==0, ставим на первую позицию тройку и требуем dp(i-1,K-2)>0 и т.д.. Таким образом мы можем подобрать первую цифру. Затем у нас остается перестановка из Н-1 числа и опять используем те же соображения для подбора остальных элементов. Главное помнить, какие числа мы уже поставили, чтобы они не повторялись.