Trung thu vừa rồi các em đạt giải HSG được tổ chức tham gia một buổi lễ vinh danh trao thưởng tại nhà văn hóa trung tâm thành phố. Sau buổi lễ kết thúc mỗi em
Trung thu vừa rồi các em đạt giải HSG được tổ chức tham gia một buổi lễ vinh danh trao thưởng tại nhà văn hóa trung tâm thành phố. Sau buổi lễ kết thúc mỗi em được nhận phần thưởng của mình từ ban tổ chức. Có tất cả n gói quà, giá trị các gói quà lần lượt a1,a2,...,an. Phần thưởng của mỗi em là m gói quà xếp liên tục nhau. Ban tổ chức đảm bảo phát đủ số quà cho tất cả các em. Bạn hãy lập trình tính tổng giá trị các gói quà của tất cả các em nhận được lớn nhất là bao nhiêu biết số lượng các em học sinh được nhận phần thưởng là k. Dữ liệu vào: Đọc từ tệp văn bản PRIZE.INP có cấu trúc như sau: ❖ Dòng đầu ghi ba số nguyên n, m, k (1 ≤ m.k ≤ n ≤ 5000); ❖ Dòng thứ hai ghi n số nguyên a1,a2,...,an (0 ≤ ai ≤ 10^9); ❖ Các số trong tệp cách nhau một dấu cách. Kết quả: ghi ra tệp văn bản PRIZE.OUT tổng giá trị lớn nhất của các phần thưởng. Ví dụ PRIZE.INP PRIZE.OUT 5 1 3 12 2 4 3 1 5 Giải thích: chọn các phần thưởng: [4],[3],[5] PRIZE.INP PRIZE.OUT 6 2 2 1 100 10 1000 7 99 1117 GT: chọn [100,10] , [1000,7] PASCAL
Lời giải 1 :
type int = longint;
type bool = boolean;
const MaxN = trunc(5e3);
const prefix = 'PRIZE';
fi = prefix + '.INP';
fo = prefix + '.OUT';
var a, pfs: array[0..MaxN] of int;
dp: array[0..MaxN, 0..MaxN] of int;
i, j, n, m, k: int;
ss: int64;
function range(u, v: int): int64; begin exit(pfs[v] - pfs[u - 1]); end;
function max(a, b: int): int; begin if a > b then exit(a); exit(b); end;
function min(a, b: int): int; begin if a < b then exit(a); exit(b); end;
begin
assign(input, fi); assign(output, fo);
reset(input); rewrite(output);
readln(n, m, k);
for i:=1 to n do begin
read(a[i]);
pfs[i]:=pfs[i - 1] + a[i];
end;
for i:=m to n do begin
for j:=1 to k do dp[i][j]:=dp[i - 1][j];
for j:=1 to k do begin
dp[i][j]:=max(dp[i][j], dp[i - m][j - 1] + range(i - m + 1, i));
end;
end;
writeln(dp[n][k]);
close(input); close(output);
end.
Thảo luận
Lời giải 2 :
Ok
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ự 8
Lớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần, sang năm lại là năm cuối cấp áp lực lớn dần nhưng các em vẫn phải chú ý sức khỏe nhé!
Nguồn : ADMIN :))Copyright © 2021 HOCTAP247