Матч 395, Небоскребы (Skyscrapers)

Дивизион 1, Уровень 2

Линия горизонта в городе содержит n зданий, каждое из которых имеет уникальную высоту от 1 до n. Дом виден слева (справа), если левее (правее) его нет дома с большей высотой. Например, если дома имеют порядок {1, 3, 5, 2, 4}, то слева видны дома 1, 3, 5, а справа – 4 и 5. Известно, что дома расположены так, что слева видно в точности leftSide домов, а справа – rightSide. Найти количество перестановок домов, для которых это возможно. Результат вернуть по модулю 1000000007.

Класс: Skyscrapers

Метод: int buildingCount(int n, int leftSide, int rightSide)

Ограничения: 1 £ n £ 100, 1 £ leftSide, rightSide £ n.

Вход. Количество зданий n, значения leftSide и rightSide.

Выход. Количество перестановок n домов, для которых слева видно в точности leftSide, а справа – rightSide домов.

Пример входа

n	leftSide	rightSide
3	2	2
5	3	2
8	3	2

Пример выхода

2

18

4872

РЕШЕНИЕ

комбинаторика + рекурсия

Предположим, что осталось расположить n домов, которые следует расположить так, чтобы слева было видно leftSide, а справа – rightSide домов. Пусть это можно сделать f(n, leftSide, rightSide) способами. Рассмотрим дом с наименьшей высотой. Если его поставить слева, то он будет всегда видим, а оставшиеся дома можно будет расставить f(n – 1, leftSide – 1, rightSide) способами. Если дом с наименьшей высотой поставить справа, то он всегда будет оставаться видимым справа, остальные дома можно будет расставить f(n – 1, leftSide, rightSide – 1) способами. Не с краю наименьший дом можно поставить n – 2 способами. В этом случае он не будет видим, поэтому оставшиеся дома можно расставить (n – 2) * f(n – 1, leftSide, rightSide) способами. Заметим, что при n = 1 единственная возможная расстановка будет лишь при leftSide = rightSide = 1. Получаем рекуррентное соотношение:

f(n, leftSide, rightSide) = f(n – 1, leftSide – 1, rightSide) + f(n – 1, leftSide, rightSide – 1) +

(n – 2) * f(n – 1, leftSide, rightSide),

f(1, 1, 1) = 1,

f(1, x, y) = 0, когда x и y одновременно не равны 1

ПРОГРАММА

#include <stdio.h>

#include <memory.h>

#define MAX 101

int dp[MAX][MAX][MAX];

int f(int n, int leftSide, int rightSide)

{

if (n == 1) return (leftSide == 1 && rightSide == 1) ? 1 : 0;

if ((leftSide < 1) || (rightSide < 1)) return 0;

if (dp[n][leftSide][rightSide] != -1) return dp[n][leftSide][rightSide];

dp[n][leftSide][rightSide] = (int)(((long long)f(n-1,leftSide-1,rightSide) +

(long long)f(n-1,leftSide,rightSide-1) +

(n-2)*(long long)f(n-1,leftSide,rightSide)) % 1000000007);

return dp[n][leftSide][rightSide];

}

class Skyscrapers

{

public:

int buildingCount(int n, int leftSide, int rightSide)

{

memset(dp,-1,sizeof(dp));

return f(n,leftSide,rightSide);

}

};