Giúp ý tưởng bài tập

Nhà của An là một dãy gồm 𝑛 phòng được xây dựng trên một đường thẳng và đánh số từ phòng 1 đến phòng 𝑛. Có những lò sưởi đặt tại một số phòng, phòng thứ 𝑖 có lò sưởi nếu vị trí đó đánh dấu là 1, ngược lại vị trí đó đánh dấu là 0.

Mỗi lò sưởi có một giá trị 𝑟 (tất cả các lò sưởi có 𝑟 giống nhau). Giá trị đó có nghĩa là nếu lò sưởi đặt tại vị trí 𝑖, nó có thể sưởi ấm cho tất cả các phòng trong đoạn từ [ i-r+1 , i+r-1]

An rất thích đi bộ trong nhà của mình nhưng không thích phòng không được sưởi ấm. An muốn bật một vài lò sưởi để tất cả các phòng ít nhất có một lò sưởi làm ấm phòng.

Ban đầu tất cả các lò sưởi chưa được bật. An lại không muốn phải trả quá nhiều tiền điện, vì vậy cậu ta muốn bật một số tối thiểu các lò sưởi sao cho tất cả các phòng được sưởi ấm.

Yêu cầu : Bạn hãy giúp An viết chương trình tìm số lò sưởi ít nhất cần phải bật sao cho làm ấm toàn bộ ngôi nhà?

Dữ liệu vào cho cho tệp TKD.INP

  • Dòng 1 chứa hai số 𝑛, 𝑟 (1 ≤ 𝑛, 𝑟 ≤ 1000)

  • Dòng thứ 2 chứa 𝑛 số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛 (0 ≤ 𝑎𝑖 ≤ 1, 𝑖 = 1, 𝑖 = 1, … , 𝑛). Trong đó 𝑎𝑖 = 1 nếu phòng thứ 𝑖 có đặt lò sưởi, 𝑎𝑖 = 0 nếu phòng thứ 𝑖 không có lò sưởi.

Kết quả đưa ra tệp TKD.OUT một số duy nhất là số lò sưởi ít nhất cần phải bật để sưởi ấm toàn bộ ngôi nhà. Nếu bật các lò sưởi mà vẫn không làm ấm toàn bộ ngôi nhà đưa ra -1
vd
tkd.inp
6 2
1 1 1 0 0 1
tkd.out
3

bài này dịch ra là
cho các đoạn [x_i, y_i]. tìm cách chọn các đoạn [x_i, y_i] sao cho ghép lại thành 1 đoạn [X,Y] cho trước với số đoạn nhỏ nhất
ở bài toàn này [x_i, y_i] thì bạn phải tự tính toán dựa trên mảng a
còn [X,Y][0,n - 1]

ví dụ như bài trên sẽ thành
s = [[0,1], [0,2], [1,3], [4.5]]
[X,Y] = [0,5]
-> lựa các đoạn có thể là s[1] + s[2] + s[3] = [0,1][1,3][4,5]
-> lựa chọn tối thiểu là 3

8 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?