Có N hủ kẹo dẻo được đặt trên một hàng. Ban đầu, hủ thứ i có độ ngọt là ai. Kaninho cố gắng kết hợp tất cả các hủ kẹo này thành một hủ kẹo lớn hơn. Anh ấy thực
Có N hủ kẹo dẻo được đặt trên một hàng. Ban đầu, hủ thứ i có độ ngọt là ai. Kaninho cố gắng kết hợp tất cả các hủ kẹo này thành một hủ kẹo lớn hơn. Anh ấy thực hiện phép toán dưới đây nhiều lần cho đến khi chỉ còn một hủ kẹo duy nhất thì dừng: Chọn 2 hủ kẹo kề nhau bất kì và kết hợp chúng lại thành một hủ kẹo. Hủ kẹo mới này có độ ngọt là x+y, trong đó x,y lần lượt là độ ngọt của hai hủ kẹo trước đó. Và việc này tốn chi phí là x+y. Mối quan hệ về vị trí giữa các hủ kẹo vẫn không thay đổi khi ta kết hợp chúng lại với nhau. Input: Dòng thứ nhất chứa số nguyên N(2≤N≤400) Dòng thứ hai chứa N số nguyên ai(1≤ai≤109). Output: In ra chi phí tối thiểu để kết hợp tất cả các hủ kẹo trên thành 1 hủ duy nhất. Ví dụ: Input: Copy 4 10 20 30 40 Output: Copy 190 Giải thích: Kaninho sẽ là như sau: (10,20,30,40)→(30,30,40) (Tốn chi phí: 10+20=30) (30,30,40)→(60,40) (Tốn chi phí: 30+30=60) (60,40)→(100) (Tốn chi phí: 60+40=100) Vậy tổng chỉ phí tối thiểu cần dùng là 30+60+100=190
Lời giải 1 :
Uses crt;
Var
a:array[1..500] of LongInt;
n,s,v,t,o: integer;
i: LongInt;
Begin
repeat
clrscr;
readln(n);
until (2<=n) and (n<=400);
for i:=1 to n do
begin
repeat
read(a[i]);
until (1<=a[i]) and (a[i]<1000000000);
end;
t:=0;
s:=a[1]+a[2];
repeat
o:=1;
for i:=1 to n-1 do
begin
if a[i]+a[i+1]<s then
begin
s:=a[i]+a[i+1];
o:=i;
end;
end;
a[o]:=s;
for v:=o+1 to n-1 do a[v]:=a[v+1];
t:=t+s;
s:=a[1]+a[2];
n:=n-1;
until (n=1);
writeln(t);
readln;
End.
Thảo luận
Lời giải 2 :
-
-
(10,20,30,40)→(30,30,40)(10,20,30,40)→(30,30,40) (Tốn chi phí: 10+20=30)
-
(30,30,40)→(60,40)(30,30,40)→(60,40) (Tốn chi phí: 30+30=60)
-
(60,40)→(100)(60,40)→(100) (Tốn chi phí: 60+40=100)
-
Vậy tổng chỉ phí tối thiểu cần dùng là 30+60+100=190
Có thể bạn quan tâm
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự 12
Lớp 12 - Năm cuối ở cấp tiểu học, năm học quan trọng nhất trong đời học sinh trải qua bao năm học tập, bao nhiêu kì vọng của người thân xung quanh ta. Những nỗi lo về thi đại học và định hướng tương lai thật là nặng. Hãy tin vào bản thân là mình sẽ làm được rồi tương lai mới chờ đợi các em!
Nguồn : ADMIN :))Copyright © 2021 HOCTAP247