| comun |
|
Se ştie că un subşir al unui şir se obţine eliminând zero, unul, sau mai multe elemente din şirul iniţial. Un subşir comun a două şiruri este subşir atât pentru primul, cât şi pentru al doilea şir. Să considerăm două şiruri de numere naturale x = x1, x2, ..., xM şi y = y1, y2, ..., yN care au cel puţin un subşir comun. Printre subşirurile comune există cel puţin unul maximal. De exemplu, şirurile 5,3,2 şi 7,3,5,2 au trei subşiruri comune maximale: primul este 5, 2, al doilea 3,2, iar al treilea este 5, 3. Pentru fiecare subşir comun maximal s = s1, s2, ..., sk calculăm costul subşirului astfel: pentru fiecare element si (1 <= i <= k) cost(si) = si *|pi – qi|, unde pi şi qi sunt poziţiile unde se află si în şirurile x şi respectiv y, iar |pi – qi| este valoarea absolută a diferenţei pi – qi. Costul subşirului maximal este suma costurilor elementelor subşirului, deci cost(s) = cost(s1) + cost(s2) + ... + cost(sk). Pentru exemplul de mai sus, subşirul 5, 2 are costul 5 * |3 - 1| + 2 * |4 - 3| = 12.Cerinţă Să se determine costul minim al unui subşir comun maximal.Date de intrare Fişierul de intrare comun.in conţine pe prima linie, separate printr-un spaţiu, numerele naturale M şi N, reprezentând lungimile celor două şiruri. Pe linia a doua se află M numere separate prin câte un spaţiu, reprezentând elementele primului şir. Pe linia a treia se află N numere separate prin câte un spaţiu reprezentând elementele celui de-al doilea şir.Date de ieşire Fisierul de iesire comun.out va conţine o singură linie, pe care va fi scris un singur număr natural reprezentând costul minim al unui subşir comun maximal.Restricţii
Exemple
|