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

emaxx algorithm

#algorithm#dynamic-programming#emaxx

Task

Источник: 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# solution

auto-draft, review before submit

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++ solution

matched/original

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 solution

auto-draft, review before submit

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

Explanation

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