MAXimal | |
добавлено: 11 Jun 2008 11:08 Содержание [скрыть] Динамика по профилю. Задача "паркет"Типичными задачами на динамику по профилю, являются:
Задача "Паркет"Имеется прямоугольная площадь размером NxM. Нужно найти количество способов замостить эту площадь фигурами 1x2 (пустых клеток не должно оставаться, фигуры не должны накладываться друг на друга). Построим такую динамику: D[I][Mask], где I=1..N, Mask=0..2^M-1. I обозначает количество строк в текущем поле, а Mask - профиль последней строки в текущем поле. Если j-й бит в Mask равен нулю, то в этом месте профиль проходит на "нормальном уровне", а если 1 - то здесь "выемка" глубиной 1. Ответом, очевидно, будет D[N][0]. Строить такую динамику будем, просто перебирая все I=1..N, все маски Mask=0..2^M-1, и для каждой маски будем делать переходы вперёд, т.е. добавлять к ней новую фигуру всеми возможными способами. Реализация: int n, m; vector < vector<long long> > d; void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0) { if (x == n) return; if (y >= m) d[x+1][next_mask] += d[x][mask]; else { int my_mask = 1 << y; if (mask & my_mask) calc (x, y+1, mask, next_mask); else { calc (x, y+1, mask, next_mask | my_mask); if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1))) calc (x, y+2, mask, next_mask); } } } int main() { cin >> n >> m; d.resize (n+1, vector<long long> (1<<m)); d[0][0] = 1; for (int x=0; x<n; ++x) for (int mask=0; mask<(1<<m); ++mask) calc (x, 0, mask, 0); cout << d[n][0]; }
|