Evident, putem încerca o soluţie identică cu cea a '$Problemei 1$':probleme-de-acoperire-2#problema1, 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 fi iniţial 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 din 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 &le; 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 fi iniţial 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 din 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 &le; 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 ş.a.m.d.):

p=. !probleme-de-acoperire-2?P273.jpg!

Dacă decidem să nu punem piesă în pătrăţelul $(4, 3)$ atunci din starea $(4, 3, 1000212)$ trecem în starea $(5, 3, 10000212)$.

Dacă decidem să nu punem piesă în pătrăţelul $(4, 3)$ atunci din starea $(4, 3, 1000212)$ trecem în starea $(5, 3, 1000212)$.

p=. !probleme-de-acoperire-2?P274.jpg!

p=. !probleme-de-acoperire-2?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$':probleme-de-acoperire-2#prob2, '$3$':probleme-de-acoperire-2#prob3 şi '$4$':probleme-de-acoperire-2#prob4 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$':probleme-de-acoperire-2#problema2, '$3$':probleme-de-acoperire-2#problema3 şi '$4$':probleme-de-acoperire-2#problema4 pot fi rezolvate în mod asemănător în complexitate $O(N * M * 2^M^)$.

h2(#problema8). Problema 8 (Lot 2001, 'SGU Domino':http://acm.sgu.ru/problem.php?contest=0&problem=101, 'IPSC 2004':http://ipsc.ksp.sk/contests/ipsc2004/practice/problems/t.php, Algoritmus 2005, IOI 2005)

p=. !probleme-de-acoperire-2?P282.jpg!

Acum vedem că un domino amplasat pe tablă trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele, iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, facem observaţia că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face ca să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii neadiacente de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de $cuplaj maxim într-un graf bipartit$. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

Acum vedem că un domino amplasat pe tablă trebuie să ocupe o celulă colorată alb şi una negru, celule care sunt adiacente. Dacă realizăm un graf în care nodurile sunt celulele, iar între două noduri există muchie dacă ele sunt adiacente vertical sau orizontal pe tablă, observăm că graful este bipartit. O acoperire cu dominouri corespunde în acest graf unei mulţimi de muchii pentru care nu există două muchii cu acelaşi capăt (o muchie corespunde amplasării posibile a unui domino, iar restricţia menţionată face să nu existe dominouri care se suprapun). Deci pentru a găsi o soluţie maximală pentru problema iniţială, trebuie să găsim o mulţime de muchii neadiacente de cardinal maxim. În acest mod am transformat cerinţa într-o problemă clasică de teoria grafurilor cunoscută sub numele de $cuplaj maxim într-un graf bipartit$. Vedem în imaginea următoare cum a fost transformată tabla într-un graf şi cum soluţia prezentată în exemplu corespunde unui $cuplaj maxim$ în graful asociat tablei.

p=. !probleme-de-acoperire-2?P283.jpg!