Cho một dãy bao gồm n (1 1, A2, …, An cùng số nguyên dương k (k Input: tệp tin văn bản SUBSEQ.INPDòng 1: Chứa số nDòng 2: Chứa hẹn n số A1, A2, …, An giải pháp nhau ít nhất một vết cách
Dòng 1: Ghi độ nhiều năm dãy con kiếm tìm đượcCác cái tiếp: Ghi các bộ phận được lựa chọn vào hàng conDòng cuối: Ghi tổng các phần tử của hàng con đó.

Bạn đang xem: Dãy con dài nhất có tổng chia hết cho k

SUBSEQ.INPSUBSEQ.OUT10 581 6 11 5 10 15 đôi mươi 2 4 9a<10> = 9 a<9> = 4 a<7> = 20 a<6> = 15 a<5> = 10 a<4> = 5 a<3> = 11 a<2> = 6 Sum = 80

3.4.1. Cách giải 1

Đề bài bác đề nghị chọn ra một vài buổi tối nhiều các phần tử vào dãy A sẽ được một dãy bao gồm tổng chia hết cho k, ta rất có thể giải bài xích toán bằng phương thức chú tâm tổ hợp bởi xoay lui có reviews nhánh cận nhằm mục đích giảm sút chi phí vào chuyên môn vét cạn. Dưới phía trên ta trình diễn cách thức quy hướng động:Nhận xét 1: Không ảnh hưởng mang đến công dụng sau cùng, ta rất có thể đặt: Ai := Ai hack k với mọi i: 1 Nhận xét 2: Hotline S là tổng các bộ phận vào mảng A, ta có thể biến đổi giải pháp tiếp cận bài toán: vậy vày tìm kiếm xem đề nghị chọn ra một trong những về tối đa phần đông phần tử để sở hữu tổng phân tách hết cho k, ta sẽ chọn ra một trong những buổi tối tphát âm những thành phần tất cả tổng đồng dư cùng với S theo modul k. lúc đó chỉ cần thải trừ hầu như bộ phận này thì các phần tử sót lại đã là công dụng.Nhận xét 3: Số phần tử tối tphát âm đề nghị vứt bỏ bao giờ cũng nhỏ hơn kThật vậy, giả sử số bộ phận tối thiểu buộc phải loại bỏ là m với các phần tử yêu cầu đào thải là Ai1, Ai2, …, Aim. Các thành phần này còn có tổng đồng dư cùng với S theo mô-đun k.Xét các dãy sau:Dãy 0 := () = Dãy rỗng (Tổng = 0 (thủ thuật k))Dãy 1 := (Ai1) Dãy 2 := (Ai1, Ai2)Dãy 3 := (Ai1, Ai2, Ai3)… …Dãy m := (Ai1, Ai2, …, Aim)vì thế tất cả m + 1 hàng, nếu như m >= k thì theo nguyên tắc Dirichlet đã vĩnh cửu nhì hàng gồm tổng đồng dư theo mô-đun k. Giả sử chính là nhì dãy:Ai1 + Ai2 + … + Aip = Ai1 + Ai2 + … + Aip + Aip+1 + … + Aiq (gian lận k)Suy ra Aip+1 + … + Aiq phân chia hết mang đến k. Vậy ta có thể xoá không còn các phần tử này vào hàng vẫn chọn cơ mà vẫn được một hàng bao gồm tổng đồng dư với S theo modul k, mâu thuẫn cùng với trả thiết là hàng đã lựa chọn tất cả số thành phần tối tđọc.

Xem thêm: Confidential Information Là Gì ? Confidential Information Là Gì


Công thức truy nã hồi:Nếu ta call F là số bộ phận về tối tphát âm đề nghị lựa chọn trong hàng A1, A2, …, Ai để có tổng chia k dư t. Nếu không tồn tại phương pháp lựa chọn ta coi F
*
. Khi đó F được xem qua công thức truy vấn hồi sau:Nếu trong hàng bên trên chưa phải lựa chọn Ai thì F = F;Nếu vào hàng trên nên lựa chọn Ai thì F = 1 + F*
> (
*
 sinh sống đây hiểu là phép trừ bên trên những lớp đồng dư gian lận k. lấy một ví dụ lúc k = 7 thì 
*
= 5).Từ trên suy ra F = min (F, 1 + F).Còn tất yếu, cơ sở quy hoạch động: F(0, 0) = 0; F(0, i) = 
*
(với "i: 1 Bảng cách thực hiện F tất cả kích cỡ <0..n, 0.. k - 1> tối nhiều là 1001x50 phần tử dạng hình Byte.P_3_03_5.PAS * Dãy bé có tổng phân tách không còn cho kprogram SubSequence;const InputFile = 'SUBSEQ.INP'; OutputFile = 'SUBSEQ.OUT'; maxN = 1000; maxK = 50;var a: array<1..maxN> of Integer; f: array<0..maxN, 0..maxK - 1> of Byte; n, k: Integer;procedure Enter;var fi: Text; i: Integer;begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, k); for i := 1 lớn n vì chưng Read(fi, a); Close(fi);end;function Sub(x, y: Integer): Integer; Tính x - y (theo thủ thuật k)var tmp: Integer;begin tmp := (x - y) gian lận k; if tmp >= 0 then Sub := tmp else Sub := tmp + k;end;procedure Optimize;var i, t: Integer;begin FillChar(f, SizeOf(f), $FF); Khởi tạo ra những thành phần f<0, .> gần như bởi 255 () f<0, 0> := 0; Ngoại trừ f<0, 0> := 0 for i := 1 khổng lồ n vày for t := 0 khổng lồ k - 1 vày Tính f := min (f, f + 1 if f f)> + 1 then f := f else f := f)> + 1;end;procedure Result;var fo: Text; i, t: Integer; SumAll, Sum: LongInt;begin SumAll := 0; for i := 1 to n bởi vì SumAll := SumAll + a; Assign(fo, OutputFile); Rewrite(fo); WriteLn(fo, n - f); n - số phần tử vứt đi = số bộ phận giữ lại i := n; t := SumAll mod k; Sum := 0; for i := n downto 1 bởi vì if f = f then Nếu phương pháp về tối ưu không quăng quật ai, tức là gồm chọn ai begin WriteLn(fo, 'a<', i, '> = ', a); Sum := Sum + a; kết thúc else t := Sub(t, a); WriteLn(fo, 'Sum = ', Sum); Close(fo);end;begin Enter; Optimize; Result;kết thúc.

3.4.2. Cách giải 2

Phân những bộ phận trong hàng a theo những lớp đồng dư modul k. Lớp i bao gồm những thành phần phân tách k dư i. hotline Count là số lượng những bộ phận trực thuộc lớp i.Với 0 Ta dễ thấy rằng f<0, 0> = Count<0>, Trace<0, 0> = Count<0>, còn Trace<0, i> với i khác 0 bằng -1. Với i >= 1; 0 Từ đó suy ra bí quyết tầm nã hồi:
*

P_3_03_6.PAS * Dãy con có tổng phân tách không còn cho kprogram SubSequence;const InputFile = 'SUBSEQ.INP'; OutputFile = 'SUBSEQ.OUT'; maxN = 1000; maxK = 50;var a: array<1..maxN> of Integer; Count: array<0..maxK - 1> of Integer; f, Trace: array<0..maxK - 1, 0..maxK - 1> of Integer; n, k: Integer;procedure Enter;var fi: Text; i: Integer;begin Assign(fi, InputFile); Reset(fi); ReadLn(fi, n, k); FillChar(Count, SizeOf(Count), 0); for i := 1 khổng lồ n vị begin Read(fi, a); Inc(Count gian lận k>); Nhập dữ liệu đôi khi với việc tính những Count<.> end; Close(fi);end;function Sub(x, y: Integer): Integer;var tmp: Integer;begin tmp := (x - y) gian lận k; if tmp >= 0 then Sub := tmp else Sub := tmp + k;end;procedure Optimize;var i, j, t: Integer;begin FillChar(f, SizeOf(f), 0); f<0, 0> := Count<0>; FillChar(Trace, SizeOf(Trace), $FF); Khởi chế tạo ra các mảng Trace=-1 Trace<0, 0> := Count<0>; Ngoại trừ Trace<0, 0> = Count<0> for i := 1 to k - 1 vày for t := 0 khổng lồ k - 1 vì chưng for j := 0 to Count vì if (Trace -1) and (f f + j) then begin f := f + j; Trace := j; end;end;procedure Result;var fo: Text; i, t, j: Integer; Sum: LongInt;begin t := 0; Tính lại những Count := Số bộ phận phương án về tối ưu vẫn chọn vào lớp i for i := k - 1 downkhổng lồ 0 vày begin j := Trace; t := Sub(t, j * i); Count := j; end; Assign(fo, OutputFile); Rewrite(fo); WriteLn(fo, f); Sum := 0; for i := 1 to n vì chưng begin t := a gian lận k; if Count > 0 then begin WriteLn(fo, 'a<', i, '> = ', a); Dec(Count); Sum := Sum + a; end; end; WriteLn(fo, 'Sum = ', Sum); Close(fo);end;begin Enter; Optimize; Result;kết thúc.Cách giải đồ vật hai xuất sắc hơn phương pháp giải đầu tiên bởi nó có thể triển khai với n Khủng. Ví dụ này cho thấy một bài xích toán quy hướng cồn hoàn toàn có thể có tương đối nhiều giải pháp đặt phương pháp truy nã hồi để giải.
Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *