Programación Dinámica sobre perfil roto. Problema “Parquet”

Problemas comunes resueltos usando DP sobre perfil roto incluyen:

encontrar la cantidad de formas de llenar completamente un área (p. ej. un tablero/grilla) con algunas figuras (p. ej. dominós)
encontrar una forma de llenar un área con el mínimo número de figuras
encontrar un llenado parcial con el mínimo de espacio sin llenar (o celdas, en el caso de una grilla)
encontrar un llenado parcial con el mínimo número de figuras, tal que no se puedan agregar más figuras

Problema “Parquet”

Descripción del problema. Dada una grilla de tamaño $N \times M$ . Encontrar la cantidad de formas de llenar la grilla con figuras de tamaño $2 \times 1$ (ninguna celda debe quedar sin llenar, y las figuras no deben solaparse).

Sea el estado de DP: $dp[i, mask]$ , donde $i = 1, \ldots N$ y $mask = 0, \ldots 2^M - 1$ .

$i$ representa la cantidad de filas en la grilla actual, y $mask$ es el estado de la última fila de la grilla actual. Si el $j$ -ésimo bit de $mask$ es $0$ entonces la celda correspondiente está llena; si no, está vacía.

Claramente, la respuesta al problema será $dp[N, 0]$ .

Vamos a construir el estado de DP iterando sobre cada $i = 1, \cdots N$ y cada $mask = 0, \ldots 2^M - 1$ , y para cada $mask$ solo vamos a hacer transiciones hacia adelante, es decir, vamos a agregar figuras a la grilla actual.

Implementación


int n, m;
vector < vector<long long> > dp;
 
 
void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
{
	if (x == n)
		return;
	if (y >= m)
		dp[x+1][next_mask] += dp[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;
 
	dp.resize (n+1, vector<long long> (1<<m));
	dp[0][0] = 1;
	for (int x=0; x<n; ++x)
		for (int mask=0; mask<(1<<m); ++mask)
			calc (x, 0, mask, 0);
 
	cout << dp[n][0];
 
}

Programación Dinámica sobre perfil roto. Problema “Parquet”

Problema “Parquet”

Implementación

Problemas de práctica

Referencias