Pitici4

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]).