dãy con dài nhất có tổng chia hết cho k

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