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

e-maxx algorithm original: C/C++ #algorithm #dynamic-programming #emaxx

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

Static

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

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

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

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

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

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

Tarefa "Паркет"

Имеется прямоугольная площадь размером NxM. Нужно find количество способов замостить эту площадь фигурами 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, и для каждой маски будем делать переходы вперёд, т.е. добавлять к ней новую фигуру всеми возможными способами. Implementação:

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# solução

rascunho automático, revisar antes de enviar

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++ solução

correspondente/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 solução

rascunho automático, revisar antes de enviar

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

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

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.