Consideram un sir de N
numere naturale distincte x1,
x2, ... xN. Vom numi reducere de lungime p
eliminarea de la unul dintre cele doua capete ale sirului a secventei formate
din primele, respectiv ultimele p
elemente din sir. Mai exact, o reducere de lungime p
consta fie din eliminarea elementelor x1,
x2, ...,xp, fie eliminarea elementelor xN-p+1,
xN-p+2, ..., xN. Evident, dupa reducere, sirul
devine mai scurt cu p elemente.
Sirului obtinut in
urma reducerii i se pot aplica in continuare operatii de reducere de diferite
lungimi, procedeul continuand pana cand sir devine vid.
Costul unei reduceri se calculeaza ca fiind diferenta absoluta dintre elementele
de la capetele secventei care se elimina inmultita cu numarul de elemente ale
secventei. Presupunand ca reducerea este formata din secventa xi,
xi+1, ..., xk, atunci costul reducerii este |xi
– xk|*(i-k+1). Daca reducerea este de lungime 1,
atunci costul sau este dat de valoarea elementului eliminat. Costul total al
reducerilor este dat de suma tuturor reducerilor aplicate sirului.
Cerinta
Sa se determine costul total
maxim al reducerilor aplicate sirului.
Date de intrare
Fisierul de intrare reduceri.in
contine pe prima linie numarul natural N,
iar pe urmatoarea linie se afla N
numere naturale distincte separate prin cate un spatiu, reprezentand sirul.
Date de iesire
Fisierul reduceri.out
va contine o singura linie pe care va fi scris costul total maxim care se poate
obtine aplicand reduceri succesive sirului.
Restrictii si precizari
3<=N<=100
Elementele sirului
sunt numere naturale distincte si nenule din intervalul 1..1000.
Poate fi aplicata
sirului o singura reducere, care consta in eliminarea intregului sir.
Exemplu
reduceri.in
reduceri.out
Explicatii
6
54 29 196 21 133 118
768
Se vor efectua 3 reduceri.
Prima reducere: se elimina primele 3 elemente cu un cost de 426.
A doua reducere: se elimina ultimul element, cu un cost de 118.
Ultima reducere: se elimina ce a ramas din sir, adica 21
si 133, cu un cost de 224.
Costul total este 426+118+224=768
prof.
Dan Pracsiu
Gr. Sc. Ind. “Stefan Procopiu” Vaslui
Contact: dpracsiu@yahoo.com