MAXimal | |
добавлено: 11 Jun 2008 11:18 Содержание [скрыть] Расстановка слонов на шахматной доскеТребуется найти количество способов расставить K слонов на доске размером NxN. АлгоритмРешать задачу будем с помощью динамического программирования. Пусть D[i][j] - количество способов расставить j слонов на диагоналях до i-ой включительно, причём только тех диагоналях, которые того же цвета, что и i-ая диагональ. Тогда i = 1..2N-1, j = 0..K. Диагонали занумеруем следующим образом (пример для доски 5x5): черные: белые: 1 _ 5 _ 9 _ 2 _ 6 _ _ 5 _ 9 _ 2 _ 6 _ 8 5 _ 9 _ 7 _ 6 _ 8 _ _ 9 _ 7 _ 6 _ 8 _ 4 9 _ 7 _ 3 _ 8 _ 4 _ Т.е. нечётные номера соответствуют чёрным диагоналям, чётные - белым; диагонали нумеруем в порядке увеличения количества элементов в них. При такой нумерации мы можем вычислить каждое D[i][], основываясь только на D[i-2][] (двойка вычитается, чтобы мы рассматривали диагональ того же цвета). Итак, пусть текущий элемент динамики - D[i][j]. Имеем два перехода. Первый - D[i-2][j], т.е. ставим всех j слонов на предыдущие диагонали. Второй переход - если мы ставим одного слона на текущую диагональ, а остальных j-1 слонов - на предыдущие; заметим, что количество способов поставить слона на текущую диагональ равно количеству клеток в ней минус j-1, т.к. слоны, стоящие на предыдущих диагоналях, будут перекрывать часть направлений. Таким образом, имеем: D[i][j] = D[i-2][j] + D[i-2][j-1] (cells(i) - j + 1) где cells(i) - количество клеток, лежащих на i-ой диагонали. Например, cells можно вычислять так:
int cells (int i) { if (i & 1) return i / 4 * 2 + 1; else return (i - 1) / 4 * 2 + 2; } Осталось определить базу динамики, тут никаких сложностей нет: D[i][0] = 1, D[1][1] = 1. Наконец, вычислив динамику, найти собственно ответ к задаче несложно. Перебираем количество i=0..K слонов, стоящих на чёрных диагоналях (номер последней чёрной диагонали - 2N-1), соответственно K-i слонов ставим на белые диагонали (номер последней белой диагонали - 2N-2), т.е. к ответу прибавляем величину D[2N-1][i] * D[2N-2][K-i]. Реализацияint n, k; // входные данные if (k > 2*n-1) { cout << 0; return 0; } vector < vector<int> > d (n*2, vector<int> (k+2)); for (int i=0; i<n*2; ++i) d[i][0] = 1; d[1][1] = 1; for (int i=2; i<n*2; ++i) for (int j=1; j<=k; ++j) d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1); int ans = 0; for (int i=0; i<=k; ++i) ans += d[n*2-1][i] * d[n*2-2][k-i]; cout << ans;
|