h3(#problema-1). Problema 1: 'Be a Smart Raftsman':http://acm.sgu.ru/problem.php?contest=0&problem=475 (SGU)

bq. Sunteţi membri ai unui echipaj de rafting care constă din $N ≤ 10$ participanţi. Puteţi naviga pe râu, şi scopul tău este să treci de $M ≤ 1000$ curenţii consecutivi şi să ajungi de la punctul de început la punctul de sfârşit în timp minim. Cel de-al $i$-lea curent se caracterizează prin greutatea critică $c{~i~}$, iar al $j$-lea participant este caracterizat greutatea sa $w{~j~}$. În cazul în care pluta trece prin al $i$-lea curent cu oameni la bord cu greutatea totală mai mare de $c{~i~}$, ea se răstoarnă. Această parte a rafting-ului este cea mai interesantă, dar este nevoie de timp suplimentar pentru a te urca pe plută după răsturnare. Deci, uneori este mai bine să se urce un grup de oameni cu greutate totală care nu depăşeşte greutatea critică de pe plută, în timp ce restul parcurg distanţa pe jos.
Mai formal, vom considera $m + 1$ puncte $P{~0~}, P{~1~} ,..., P{~M~}$, în cazul în care $P{~0~}$ este începutul şi $P{~M~}$ este punctul final. Fiecare dintre punctele intermediare $P{~i~} (1 ≤ i ≤ M-1)$ este situat între $i$-lea şi $(i + 1)$-lea curent. Dacă pluta se răstoarnă, sunt necesare $D{~i~}$ minute pentru a ajunge de la $P{~i-1~}$ la $P{~I~}$, altfel sunt necesare $d{~i~}$ minute. Cel de-al $j$-lea participant poate merge pe jos de la $P{~i-1~}$ la $P{~I~}$ în $t{~j~}$ minute, iar pentru a se urca sau a coborî din plută are nevoie de $s{~j~}$ minute. Înainte de fiecare dintre riffles grupului dvs. este împărţit în două părţi. Plute prima parte, prin intermediul riffle (cu sau fără răsturnare), şi a doua parte se duce pe malul de la următorul punct intermediar. În acest moment, ei întotdeauna a º teptare pentru pluta, sau plută aşteaptă pentru toate pietoni, în cazul în care ajunge mai devreme. Apoi, unii participanti care sunt pe pluta se poate da jos, iar unii participanti care sunt pe banca poate obţine de pe pluta. Ele nu pot începe să faci înainte de pluta, precum şi toate drumeţii ajung la punct. Timpul total necesar pentru această acţiune este egală cu suma de SJ pentru persoanele schimba locul lor. Apoi treci riffle următoare şi aşa mai departe, până când veţi ajunge la linia de sosire. Reţineţi că nimeni nu poate începe deplasarea la următorul punct de locuri, până când alţii s-au schimbat.
Amintiţi-vă, că sa incepeti de la punctul de P0, având toate grupul dvs. de pe malul (nu pe pluta), şi trebuie să terminaţi la punctul de pm, de asemenea, cu toţi participanţii de pe banca si pluta, cu tine. Nu vi se permite să părăsească pluta, la începutul sau de la un punct intermediar, precum şi mers pe jos spre linia de sosire, fără ea. Aveţi posibilitatea să ia toate grupul de salvare să treacă un riffle, dar nu puteţi lăsa pluta goale în timpul călătoriei. Sarcina ta este de a calcula timpul minim necesar pentru a ajunge la linia de sosire.

h2. Programare dinamica folosind vectori de numere intregi