Trong kỳ thi học sinh giỏi môn Tin học, em là người đạt giải đặc biệt. Ban tổ chức cho phép em chọn các phần thưởng cho mình. Các phần thưởng xếp thành một dãy được đánh số từ 1 đến N (0 ≤ N ≤ 10000), phần thưởng thứ i có giá trị là ai (1 ≤ ai ≤ 100). Em được phép chọn các phần thưởng cho mình theo nguyên tắc không chọn 3 phần thưởng liên tiếp nhau trong dãy. Em hãy lập chương trình chọn ra các phần thưởng sao cho tổng giá trị của các phần thưởng nhận được là lớn nhất.
Dữ liệu: Cho trong file PTHUONG.INP gồm các dòng:
- Dòng đầu tiên là số phần thưởng N.
- Dòng tiếp theo ghi N số ai (1 ≤ i ≤ N).
Kết quả: Ghi ra file PTHUONG.OUT gồm ba dòng:
- Dòng đầu ghi tổng giá trị lớn nhất của các phần thưởng đã chọn và số lượng các phần tử được chọn đó.
- Dòng tiếp theo ghi vị trí của các phần thưởng đã chọn theo thứ tự trong dãy.
- Dòng cuối cùng ghi giá trị của các phần thưởng đã chọn theo thứ tự trong dãy.
Ví dụ:
| PTHUONG.INP | PTHUONG.OUT |
|
7 6 9 1 3 5 10 4 |
32 5 1 2 4 6 7 6 9 3 10 4 |
uses crt;
type mang= array[0..10000 ] of byte;
var a,d,m:mang; dd:array[1..20,1..400] of byte;
b:array [1..10000] of boolean;
r,dem, t,n,max,i,j:integer;
f:text;
procedure doc;
var i:integer;
begin
assign(f,'pthuong.inp');
reset(f);
readln(f,n);
for i:=1 to n do
readln(f,d[i]);
close(f);
end;
function kt( c:mang):boolean;
var i,j:longint;
q:boolean;
begin
i:=1;
q:=true;
while (i<=r-2) and q do
begin
j:=1;
while c[i+j-1]+1=c[i+j] do
j:=j+1;
if j>=3 then q:=false else q:=true;
i:=i+1;
end;
kt:=q;
end;
Procedure print;
var i,tong: byte;
begin if kt(a)=true then
begin dem:=dem+1;
tong:=0;
for i:=1 to r do
begin
dd[dem,i]:= a[i];
tong:=tong+d[a[i]];
end; m[dem]:=tong;
end;
end;
Procedure Find(k:byte);
var j: byte;
begin
if k>r then print else
begin
for j:=1 to n do
if b[j] and (j>a[k-1]) then
begin
a[k]:=j; b[j]:=false;
Find(k+1);
b[j]:=true;
end;
end;
end;
begin
clrscr;
doc;
dem:=0;
r:= n-(n div 3);
for t:=1 to n do
b[t]:=true; a[0]:=0;
Find(1);
max:=m[1];
for i:=1 to dem do
if max< m[i] then max:=m[i];
assign(f,'PTHUONG.OUT');
rewrite(f);
writeln(f,max);
for i:=1 to dem do
if max=m[i] then
begin
j:=1;
while (dd[i,j] <>0) do
begin
write(f,dd[i,j]:2);
j:=j+1;
end;
end;
close(f);
end.
Bạn tham khảo bộ code này nhé.
