reduceri
Да
разгледаме
редица от N различни
цели
положителни
числа x1, x2, ... xN. Премахването
на p на
брой числа от
редицата, всичките
намиращи се или
в началото на
редицатат
или в нейния
край, наричаме
p-редукция. С
други думи, една
p-редукция се
състои или в
премахване на
елементите x1, x2, ...,xp, или
в премахване на
xN-p+1, xN-p+2, ..., xN. Очевидно,
след
редукцията
редицата
става по-къса
с p елемента.
Към редица, получена
след редукция
може да се приложи
нова редукция
или
последователност
от редукции с
различни
дължини. Това
може да се
повтаря,
докато
редицата не е
празна.
Цената на
една
редукция се
пресмята
като абсолютната
стойност на
разликата
между
елементите
от краищата
на
премахнатата
подредица,
умножена по броя
на
премахнатите
елементи. Например,
ако
редукцията е
премахнала xi, xi+1, ..., xk,
тогава цената
й е |xi – xk|*(i-k+1). В случая,
когато
редукцията е
с дължина 1,
цената й е
равна на стойността
на
премахнатия
елемент. Общата
цена на
последователност
от редукции е
равна на
сумата от
цените на
всичките редукции.
Задача
Определете
максималната
цена на
всички редукции,
които могат
да се
приложат последователно
към дадена
редица.
Вход
Входният
файл reduceri.in съдържа
в първия си
ред едно цяло
положително
число N. На
следващия
ред е
записана
дадената
редица,
състояща се
от N различни
цели
положителни
числа.
Изход
Файлът reduceri.out трябва
да съдържа
един ред, на
който е записана
общата
максимална
цена,
получаваща
се при прилагането
на
последователност
от редукции
върху
дадената
редица.
Ограничения
и пояснения
3<=N<=100
Елементите
на дадената
редица са
различни
строго
положителни
цели числа от
интервала 1..1000.
Възможно е и прилагането
на една единствена
редукция, с която
се премахва цялата
дадена редица.
Промер
reduceri.in |
reduceri.out |
Обяснение |
6 |
768 |
Трябва да се направят 3 редукции. Първата редукцията премахва първите 3 елемента на цена 426. Втората редукция премахва последния елемент на цена 118. Третата редукция премахва всичко, което е останало от редицата, а именно 21 и 133, и има цена 224. Общата цена е 426+118+224=768 |
Време за
работа на
програмата: 0.1 сек.за
тест
prof. Dan Pracsiu
Industrial School Group “ªtefan Procopiu”
Vaslui
Contact: dpracsiu@yahoo.com
Превод
на български:
Емил
Келеведжиев