h1(#pitici4). 'Pitici4':problema/pitici4

Observăm că este util să ordonăm piticii după informaţiile furnizate; mai exact, în funcţie de numărul de pitici pe care aceştia susţin că îl văd în faţa lor. Apoi vom folosi metoda programării dinamice pentru a răspunsul căutat.

Observăm că este util să ordonăm piticii în funcţie de $A$ şi în caz de egalitate în funcţie de $B$ pentru ca piticii cu aceleaşi informaţii să fie grupaţi. Vom folosi apoi metoda programării dinamice pentru a determina răspunsul căutat. Fie $C[i] = numărul maxim de pitici a căror informaţii nu se contrazic care aparţin unor grupuri care se termină înainte de poziţia i$. Pentru a obţine recurenţa, ne gândim că la poziţia $i+1$ vom încerca să formăm un nou grup. Are rost să luăm în considerare în acest moment doar acei pitici $j$ cu propritatea că $A[j] = i$. Găsirea acestora nu presupune o iteraţie liniară, datorită sortării iniţiale. Vom crea mai multe grupuri noi conţinând piticii cu acelaşi $B$. Să presupunem că un astfel de grup conţine $nr$ pitici. Atunci recurenţa va fi $C[N-B[j]] = max(C[N-B[j]], C[i] + min(N-A[j]-B[j], nr))$, deoarece grupul se va termina la poziţia $N-B[j]$ şi numărul de pitici din noul grup nu poate depăşi $N-A[j]-B[j]$. Nu trebuie uitat cazul în care grupul format conţine un singur pitic care minte, caz banal de tratat: $C[i+1] = max(C[i+1], C[i])$.

private

public