Arxeoloqlar

Xəzinə ovçuları komandanız yeni bir arxeoloji abidə kəşf edib. Bu abidə qiymətli metallar və qədim əşyalarla doludur və bir xətt boyunca yerləşən $n$ qazıntı yerindən ibarətdir.

İlkin planlara əsasən, hər bir qazıntı yerinin xalis mənfəət gətirəcəyi gözlənilir. $i$-ci yerin mənfəəti p_i ilə ifadə olunur. Bu o deməkdir ki, komandanız $i$-ci yerdə qazılan hər metr üçün p_i dollar qazanacaq. Qeyd etmək lazımdır ki, p_i mənfi də ola bilər, bu isə həmin yerdə qazıntı texnikasının istismar xərclərinin qazıntıdan əldə edilən faktiki faydanı üstələdiyini göstərir.

Ən gəlirli yerlərdə mümkün qədər çox qazmaq istəyəcəksiniz. Lakin, sürüşmələrin qarşısını almaq üçün çox dik yamaclar olmamalıdır. Dəqiq desək, hər hansı iki qonşu nöqtə üçün bu nöqtələrdə qazma dərinliyi arasındakı fərq 1 metrdən çox ola bilməz. Xüsusilə, 1 və $n$ yerləri yalnız 1 metr dərinliyə qədər qazıla bilər.

Bu şərtlər altında maksimum xalis mənfəəti nə qədər əldə edə bilərsiniz?

Məsələn, aşağıda birinci nümunə üçün optimal olan qazıntı planı təsvir edilmişdir. Belə bir planın xalis mənfəəti $8$-ə bərabərdir.