Evident, putem încerca o soluţie identică cu cea a '$Problemei 1$':probleme-de-acoperire2#prob1, dar aici limitele sunt puţin mai mari şi avem nevoie de un algoritm mai eficient.

Există o rezolvare de complexitate $O(N * M * 3^M^)$ care aşa cum deja v-aţi obişnuit combină metoda $backtracking$ cu metoda $programării dinamice$. Folosim un tablou $max[N][M + 1][3^(M + 1)^]$ care conţine numărul maxim de dale puse pentru o anumită stare. Fiecare element al matricii va avea iniţial $max[i][j][config]$ egal cu $0$. Iterăm rândurile în ordinea $1 .. N$ ,coloanele în ordinea $1 .. M$ şi configuraţiile în ordine lexicografică. Când vom procesa starea reprezentată de parametrii $(i, j, config)$ vom decide dacă punem una dintre piese cu colţul de stânga sus în $(i, j)$ sau dacă lăsăm celula $(i, j)$ liberă. O stare $(i, j, config)$ se referă la un pătrăţel din matrice şi la o bandă „activă” de pătrăţele ce are lăţimea $2$. Banda conţine celulele $(i1, j + 1), (i1, j + 2)$ pentru $i1 < i$ şi celulele $(i2, j), (i2, j + 1)$ pentru $i <= i2$. Cifrele în baza $3$ ale parametrului $config$ ne spun starea perechilor de pătrate de pe banda activă: $00$ este reprezentat în $config$ de cifra $0$, $10$ de cifra $1$ şi $11$ de cifra $2$ (configuraţia $01$ nu poate apărea). De exemplu, starea $(4, 3, 1000212)$ va reprezenta configuraţia prezentată în următoarea imagine (ultima cifră corespunde primei perechi de pătrăţele, penultima cifră celei de a doua perechi şamd):

Există o rezolvare de complexitate $O(N * M * 3^M^)$ care aşa cum deja v-aţi obişnuit combină metoda $backtracking$ cu metoda $programării dinamice$. Folosim un tablou $max[N][M + 1][3^(M + 1)^]$ care conţine numărul maxim de dale puse pentru o anumită stare. Fiecare element al matricii va avea iniţial $max[i][j][config]$ egal cu $0$. Iterăm rândurile în ordinea $1 .. N$, coloanele în ordinea $1 .. M$ şi configuraţiile în ordine lexicografică. Când vom procesa starea reprezentată de parametrii $(i, j, config)$ vom decide dacă punem una dintre piese cu colţul de stânga sus în $(i, j)$ sau dacă lăsăm celula $(i, j)$ liberă. O stare $(i, j, config)$ se referă la un pătrăţel din matrice şi la o bandă „activă” de pătrăţele ce are lăţimea $2$. Banda conţine celulele $(i1, j + 1), (i1, j + 2)$ pentru $i1 < i$ şi celulele $(i2, j), (i2, j + 1)$ pentru $i <= i2$. Cifrele în baza $3$ ale parametrului $config$ ne spun starea perechilor de pătrate de pe banda activă: $00$ este reprezentat în $config$ de cifra $0$, $10$ de cifra $1$ şi $11$ de cifra $2$ (configuraţia $01$ nu poate apărea). De exemplu, starea $(4, 3, 1000212)$ va reprezenta configuraţia prezentată în următoarea imagine (ultima cifră corespunde primei perechi de pătrăţele, penultima cifră celei de a doua perechi şamd):

p=. !probleme-de-acoperire2?P273.jpg!

p=. !probleme-de-acoperire2?P276.jpg!

Tablei îi adăugăm la sfârşit o coloană pe care nu pot fi aşezate piese. Rezultatul cerut de problemă se va afla în $max[N][M + 1][0]$. Menţionăm că $Problemele 2, 3$ şi $4$ pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.

Tablei îi adăugăm la sfârşit o coloană pe care nu pot fi aşezate piese. Rezultatul cerut de problemă se va afla în $max[N][M + 1][0]$. Menţionăm că $Problemele$ '$2$':#prob2, $3$ şi $4$ pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.

h2(#prob8). Problema 8 ( _CSP 1993, Lot 2001, "Domino":http://acm.sgu.ru/problem.php?contest=0&problem=101, "The Tiling Problem":http://ipsc.ksp.sk/contests/ipsc2004/practice/problems/t.php, Algoritmus 2005, IOI 2005_ )