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

Dãy Con Dài Nhất Có Tổng Chia Hết Cho K

admin      14/06/2022

Cho một dãy có n (1 1, A2, …, An cùng số nguyên dương k (k loại 1: đựng số nDòng 2: cất n số A1, A2, …, An biện pháp nhau ít nhất một vệt cách
Dòng 1: Ghi độ dài dãy bé tìm đượcCác cái tiếp: Ghi các phần tử được lựa chọn vào hàng conDòng cuối: Ghi tổng các phần tử của dãy con đó.

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

SUBSEQ.INP

SUBSEQ.OUT

10 5

8

1 6 11 5 10 15 đôi mươi 2 4 9

a<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. Giải pháp giải 1

Đề bài yêu mong chọn ra một trong những tối nhiều các thành phần trong dãy A để được một dãy gồm tổng phân tách hết cho k, ta có thể giải bài toán bằng phương pháp duyệt tổ hợp bằng cù lui có đánh giá nhánh cận nhằm mục tiêu giảm bớt chi phí trong kỹ thuật vét cạn. Dưới đây ta trình bày phương pháp quy hoạch động:

Nhận xét 1: Không tác động đến kết quả cuối cùng, ta có thể đặt: Ai := Ai mod k với tất cả i: 1 i1, Ai2, …, Aim. Các thành phần này có tổng đồng dư cùng với S theo mô-đun k.

Xét những dãy sau:

Dãy 0 := () = hàng rỗng (Tổng = 0 (mod k))

Dãy 1 := (Ai1) dãy 2 := (Ai1, Ai2)

Dãy 3 := (Ai1, Ai2, Ai3)

… …

Dãy m := (Ai1, Ai2, …, Aim)

Như vậy gồm m + 1 dãy, giả dụ m >= k thì theo nguyên tắc Dirichlet vẫn tồn tại nhì dãy có tổng đồng dư theo mô-đun k. đưa sử chính là hai dãy:

Ai1 + Ai2 + … + Aip = Ai1 + Ai2 + … + Aip + Aip+1 + … + Aiq (mod k)

Suy ra Aip+1 + … + Aiq chia hết mang đến k. Vậy ta hoàn toàn có thể xoá hết các thành phần này trong hàng đã lựa chọn mà vẫn được một dãy có tổng đồng dư cùng với S theo modul k, mâu thuẫn với đưa thiết là dãy vẫn chọn tất cả số thành phần tối thiểu.


Công thức truy nã hồi:

Nếu ta điện thoại tư vấn F là số bộ phận tối thiểu đề nghị chọn trong dãy A1, A2, …, Ai để sở hữu tổng phân tách k dư t. Nếu không tồn tại phương án lựa chọn ta coi F =

*
. Lúc ấy F được xem qua bí quyết truy hồi sau:

Nếu trong hàng trên chưa hẳn chọn Ai thì F = F;

Nếu trong hàng trên cần chọn Ai thì F = 1 + F*

> (
*
ở đâyhiểu là phép trừ trên các lớp đồng dư mod k. Ví dụ khi k = 7 thì
*
= 5).

Xem thêm: Top Game Chơi Chung Với Bạn Bè Trên Điện Thoại Thú Vị Nhất 2021

Từ trên suy ra F = min (F, 1 + F).

Còn vớ nhiên, các đại lý quy hoạch động: F(0, 0) = 0; F(0, i) =

*
(với "i: 1 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 khổng lồ n vì Read(fi, a); Close(fi);end;function Sub(x, y: Integer): Integer; Tính x - y (theo mod k)var tmp: Integer;begin tmp := (x - y) mod 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 các thành phần f<0, .> đều bởi 255 () f<0, 0> := 0; Ngoại trừ f<0, 0> := 0 for i := 1 lớn n bởi vì for t := 0 khổng lồ k - 1 do 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ố thành phần bỏ đi = số phần tử giữ lại i := n; t := SumAll mod k; Sum := 0; for i := n downto 1 vì chưng if f = f then Nếu phương án buổi tối ưu không bỏ ai, có nghĩa là có chọn ai begin WriteLn(fo, 'a<', i, '> = ', a); Sum := Sum + a; over else t := Sub(t, a); WriteLn(fo, 'Sum = ', Sum); Close(fo);end;begin Enter; Optimize; Result;end.

3.4.2. Biện pháp giải 2

Phân các thành phần trong dãy a theo những lớp đồng dư modul k. Lớp i tất cả các bộ phận chia k dư i. Call Count là con số các phần tử thuộc lớp i.

Xem thêm: Gieo Đồng Thời 2 Con Xúc Xắc, Gieo Đồng Thời Hai Con Súc Sắc

Với 0 = 1; 0 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ày begin Read(fi, a); Inc(Count hack k>); Nhập tài liệu đồng thời 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 tạo các mảng Trace=-1 Trace<0, 0> := Count<0>; Ngoại trừ Trace<0, 0> = Count<0> for i := 1 lớn k - 1 vày for t := 0 khổng lồ k - 1 vị for j := 0 to lớn Count vì chưng if (Trace -1) và (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 các Count := Số bộ phận phương án tối ưu sẽ chọn trong lớp i for i := k - 1 downto 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 lớn n bởi begin t := a mod 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;end.Cách giải sản phẩm công nghệ hai xuất sắc hơn bí quyết giải thứ nhất vì nó rất có thể thực hiện nay với n lớn. Lấy ví dụ như này cho thấy một việc quy hoạch động gồm thể có không ít cách đặt bí quyết truy hồi để giải.

Follow Us

Có gì mới

Trending