Revizia anterioară Revizia următoare
Solutia problemei Nave Interdimensionale
Pentru primele subtaskuri vezi soluţia problemei naveplanare
Pentru 100 de puncte vom folosi un greedy în care mutăm navele pe rând pentru a obţine o linie/coloană (liniile şi coloanele sunt de fapt independente) nouă pe care se află cel puţin o navă.
Fie pentru numărul de nave care trec dinspre poziţia spre poziţia . Dacă este negativ, el va reprezenta numărul de nave care trec dinspre poziţia spre poziţia înmulţit cu .
Observăm acum că costul aferent mişcării unei nave din în cu va fi numărul de valori mai mari sau egale cu minus numărul de valori strict mai mici decât în intervalul .
De ce? Pentru că dacă este mai mare sau egal decât , înseamnă că trebuie să consumăm o secundă pentru a mişca nava între şi . Dacă este mai mic decât , am putea economisi o secundă: în loc să mişcăm nava asta spre dreapta, vom opri una dintre navele care se mişcă dinspre spre şi vom obţine acelaşi rezultat.
Există mai multe metode în Valoarea Maximă pe care o poate lua o coordonată de a găsi mişcarea cea mai ieftină. Trebuie apoi să updatăm valorile din şi să reluăm algoritmul până când numărul de linii care conţin cel puţin o navă este cel dorit.
Complexitatea finală este