Có N đống sỏi được xếp thành một hàng, đống thứ i có ai viên sỏi. Người ta có thể ghép hai đống sỏi kề nhau thành một đống và mất một chi phí thời gian có giá trị bằng tổng số viên sỏi của hai đống sỏi đó (để ghép đống sỏi thứ i thì mất ai đơn vị thời gian). Yêu cầu: Hãy viết chương trình để ghép N đống sỏi trên thành một đống sao cho tổng thời gian là lớn nhất text ghepsoi.inp 4 5 2 8 3 ghepsoi.out 43 giải thích bước 1: ghép 2 với 8 được 10 bước 2: ghép kết quả ở bước 1 là 10 với 5 được 15 bước 3: ghép kết quả ở bước 2 là 15 với 3 là 18 tổng thời gian ghép sỏi là 10+15+18=43 Cần thuật toán quy hoạch động của bài này xin thỉnh giáo cao nhân
1 câu trả lời
var i,n:longint;
a:array[0..1000007] of longint;
function f(i:longint):longint;
begin
if i = 1 then f := a[1]
else if i = 2 then f := a[1]+a[2]
else if i = 3 then f := max(max(a[1]+a[2],a[2]+a[3]),a[1]+a[3])
else f := max( max( f(i-1),f(i-2)+a[i] ), f(i-3)+a[i-1]+a[i] );
end;
begin
assign(input,'thuong.inp');reset(input);
assign(output,'thuong.out');rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
writeln(f(n));
end.
Câu hỏi trong lớp
Xem thêm
- Đề thi học kì 2 môn địa 9 có lời giải chi tiết
- Đề thi học kì 2 môn địa 9 có lời giải chi tiết
- Đề thi học kì 2 môn địa 9 có lời giải chi tiết
- Đề thi học kì 2 môn địa 9 có lời giải chi tiết giúp các em luyện tập và củng cố kiến thức hiệu quả
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 5 Địa 9 có lời giải chi tiết
