АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Хэсэг найзууд баглаа цэцэг авахыг хүссэн. Цэцэгчин нийт шинэ үйлчлүүлэгчдийн тоогоо болон олох мөнгөө байж болох хамгийн их байлгахыг хүсч байгаа. Үүнийг хийхийн тулд цэцэгчин нэг цэцэгнийхээ үнийг тухайн худалдан авагчийн өмнө нь худалдан авсан цэцэгний тоон дээр 1-ийг нэмсэн дахин нэмэхээр шийджээ. Дурын худалдан авагчийн эхний цэцэг нь анхны үнээрээ байна [(0+1)*анхны үнэ] ба 2 дахь цэцгийн үнэ нь [(1+1)*анхны үнэ] гэх мэтээр үргэлжилнэ.

Найзуудын тоо, авахыг хүссэн нийт цэцэгний тоо ба цэцэгний анхны үнэ өгөгдсөн бол бүх цэцгийг худалдан авах боломжтой хамгийн бага үнийг ол.

Жишээ нь: Хэрвээ 3 найз 4ш цэцэг худалдан авахыг хүссэн ба цэцэгний анхны үнэ тус бүр c=[1,2,3,4] бол найз тус бүр эхлээд [2,3,4] үнэтэй цэцэгнүүдийг худалдан авах ба аль нэг найз 1 үнэтэй цэцгийг дараа нь нэмж худалдан авах ба энэ үед тухайн цэцэгний үнэ (одоогийн худалдан авалт + өмнөх худалдан авалтууд)*c[0]=(1+1)*1=2. Нийт үнэ нь 2+3+4+2=11.

Функцийн тайлбар

GetMinimumCost гэдэг функцийг бичнэ үү. Нийт хэрэгтэй цэцгүүдийг худалдан авахад зарцуулагдах хамгийн бага өртгийг хэвлэх үүрэгтэй.

GetMinimumCost доорх өгөгдлийг хүлээн авна.

Оролтын бүтэц

Эхний мөрөнд n болон k тоонууд зайгаар тусгаарлагдан өгөгдөнө. Нийт худалдан авах цэцгийн тоо болон найзуудын тоо.

Хоёр дахь мөрөнд n ширхэг эерэг бүхэл тоо зайгаар тусгаарлагдан өгөгдөнө. C[i] буюу цэцэг тус бүрийн анхны үнэ.

Хязгаарлалт

1 <=n, k<= 100

1 <= c[i] <= 10⁶

Answer <2³¹

0 <= i < n

Гаралтын бүтэц

Нийт хэрэгтэй цэцгүүдийг худалдан авахад зарцуулагдах хамгийн бага өртгийг хэвлэ.

Жишээ оролт

3 3

2 5 6

Жишээ гаралт

13

Тайлбар

3 ширхэг цэцэг өгөгдсөн ба тус бүрийн үнэ харгалзан c=[2,5,6] ба нийт 3 хүн цэцэг худалдан авахаар ирсэн. Хүн бүр нэг ширхэг цэцэг худалдаж авбал нийтдээ 2+5+6=13 доллар.

Жишээ оролт

3 2

2 5 6

Жишээ гаралт

13

Тайлбар

3 ширхэг цэцэг өгөгдсөн ба тус бүрийн үнэ харгалзан c=[2,5,6] ба нийт 2 хүн цэцэг худалдан авахаар ирсэн.

1. Эхний хүн 2 цэцэг худалдан авахдаа үнэтэйгээс нь хямд руу нь худалдан авна. Ингэснээр Эхлээд 5 үнэтэй цэцгийг p1=(0+1)*5=5 үнээр, дараа нь 2 үнэтэй цэцгийг p0=(1+1)*2=4 үнээр худалдан авна.

2. Хоёр дахь хүн хамгийн үнэтэй цэцгийг худалдан авна. P2=(0+1)*6=6 үнээр худалдан авна.

Нийтдээ 5+4+6=15 үнээр худалдан авна.

Жишээ оролт

5 3

1 3 5 7 9

Жишээ гаралт

29 

Тайлбар

Найз тус бүр энэ дарааллаар цэцэг худалдан авна. 9, 7 ба 3, 5 ба 1 буюу нийт үнэ нь 9+7+3*(1+1)+5+1*(1+1)=29.

Орчуулсан : Б.Мөнхбаяр АНУ