E123. Динамика по профилю. Задача "паркет"

e-maxx algorithm оригинал: C/C++ #algorithm #dynamic-programming #emaxx

Static

Источник: e-maxx.ru/algo, страница PDF 406.

Типичными задачами на динамику по профилю, являются:

● найти количество способов замощения поля некоторыми фигурами

● найти замощение с наименьшим количеством фигур

● найти замощение с минимальным количеством неиспользованных клеток

● найти замощение с минимальным количеством фигур такое, что в него нельзя добавить ещё одну фигуру

Задача "Паркет"

Имеется прямоугольная площадь размером 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];

}

C# решение

auto-draft, проверить перед отправкой

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    int n, m;
    vector < vector<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> (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);
            Console.WriteLine( d[n][0];
    }
}

C++ решение

сопоставлено/оригинал

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];
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    int n, m;
    vector < vector<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> (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);
            System.out.println( d[n][0];
    }
}

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.