Uzb Eng

C27N. Jack monsterlarga qarshi
: 2 c
: 64

Jack bir kun labiritdan chiqish yolini izlab bir chuqurga tushib ketti. Bu chuqur atrofida monsterlar oz kursilarida otirar edilar. Ular Jackni korgan zaxotiyoq uni yoq qilmoqchi boldilar. Lekin Jackning qolida BFG 9000 nomli quroli bor edi. Uning quroli faqatgina 3 ta ketma-ket kelgan kursiga oq ota oladi. Oq otilgandan song kursilardagi monsterlar oladi, lekin qolgan monsterlar Jackga qarata oz sehrlarini ishlatib zarar yetqazadilar. Monsterlar chuqurda aylana shaklida turishibdi, Jack esa chuqurning ortasida, har bir monsterning bir marta otgadagi zarari damage[i] orqali belgilangan, shunda sizning vazifangiz Jackga yetkazilgan minimal zararni topishingiz kerak.
Masalan: 7 ta monster va ularning zararlari 3, 4, 2, 2, 1, 4, 1 bolsin.

Korib turganingizdek, monsterlar berilgan tartibda ketma-ket va aylana shaklida joylashgan, yani 1 -> 2, 2 -> 3, , 6 ->7, 7 -> 1. Rasmda ularning yetkazadigan zararlari belgilangan. Endi Jack quyidagicha ish tutsa unga monsterlar eng kam miqdorda zarar yetkaza oladi. 1- safar Jack, 1- ,2-, 3- monsterlarga qarata oq otadi va qolgan monsterlardan jami 8 birlik zarar oladi. 2 safar u 4-, 5-, 6- monsterlaga qarata oq otadi va qolgan bitta monster yani 7-si unga 1 birlik zarar yetkazadi, oxirida esa 7- monsterni yoq qiladi va Jackga minimal 9 birlik zarar yetkaziladi.

:
Birinchi qatorda monsterlar soni N beriladi (3 <= N <= 20). Ikkinchi qatorda esa N ta monsterlarning damage lari berilgan. i- son i-monsterning yetkazadigan zarari.

:
Bitta qatorda Jackning minimal oladigan zararini chiqaring.

7
3 4 2 2 1 4 1
8
4 5 6 5 4 5 6 5
9


33
:
: Adham & Sunnat


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.