Sơn tường I

-

BÀI TOÁN: TÔ MÀU BỨC TƯỜNG

Nội dung bài toán

Cho một bức tường có chiều dài n, ban đầu được sơn toàn bộ màu trắng. Bạn có k chiếc chổi sơn màu đỏ. Mỗi chiếc chổi chỉ được sử dụng một lần, nhưng có thể sơn một đoạn liên tiếp với độ dài bất kỳ.

Bạn cần sơn bức tường sao cho nó có màu sắc giống với mảng nhị phân color, trong đó:
  • color[i] = 1 nghĩa là ô tường thứ i cần được sơn màu đỏ.
  • color[i] = 0 nghĩa là ô tường thứ i cần giữ nguyên màu trắng.
Hãy tìm số lượng ô sai màu tối thiểu sau khi sử dụng k chiếc chổi sơn một cách tối ưu.

Đầu vào

Dòng đầu tiên chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 1000) — chiều dài của bức tường và số lượng chổi sơn.
Dòng thứ hai chứa n số nguyên color[i] (0 hoặc 1) mô tả màu mong muốn của từng ô trên bức tường.

Đầu ra

Một số nguyên duy nhất là số ô sai màu tối thiểu sau khi sơn với k chiếc chổi.

Ràng buộc

1 ≤ k ≤ n ≤ 1000
color[i] chỉ nhận giá trị 0 hoặc 1

Ví dụ minh họa

Ví dụ 1

Input
6 2 1 0 1 0 1 0
Output
0

Giải thích:

Có thể dùng chổi thứ nhất sơn đoạn [0, 0] và [2, 2], chổi thứ hai sơn [4, 4].
Màu sắc sau khi sơn hoàn toàn khớp với yêu cầu, số ô sai màu là 0.

Ví dụ 2

Input
5 1 1 1 1 0 0
Output
1

Giải thích:

Chỉ có 1 chổi, có thể sơn [0, 2] để đạt được color[0] = 1, color[1] = 1, color[2] = 1.
Không thể sửa được color[3] nếu nó sai màu, do đó số ô sai màu tối thiểu là 1.

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Chứng minh công thức nhị thức Newton.

-
Nhị thức Newton:  $\displaystyle (a+b)^n = \sum_{k=0}^{n} \mathrm {C}_{n}^{k} a^kb^{n-k}$    $(1)$. Chứng minh: Xét trường hợp $\displaystyle b=0$ dễ thấy $(1)$ đúng. Nếu $\displaystyle b\neq 0$, chia 2 vế của $(1)$ cho $\displaystyle b^n$, ta phải chứng minh:  $\displaystyle \left(\frac{a}{b}+1 \right)^n = \sum_{k=0}^{n}\mathrm{C}_{n}^{k}\left ( \frac{a}{b} \right )^k$. Đặt $\displaystyle x=\frac{a}{b}$, ta được:  $\displaystyle \left(x+1\right)^n=\sum_{k=0}^{n}\mathrm{C}_{n}^{k}x^k$    $(2)$. Ta viết: $\displaystyle \left ( x+1 \right )^n=(x+1)(x+1)...(x+1)$ $(\displaystyle n$ thừa số $\displaystyle (x+1))$. Số hạng tử $\displaystyle x^k$ trong khai triển $(2)$ chính là số cách chọn ra $\displaystyle k$ số $\displaystyle x$ từ $\displaystyle n$ thừa số $\displaystyle (x+1)$ ở trên và đem nhân lại với nhau.  Có $\displaystyle \mathrm{C}_{n}^{k}$ cách chọn ra hạng tử $\displaystyle x^k$ ấy, suy ra, có  $\mathrm{C}_{n}^{k}x^k$  tron...
Đọc thêm

Lý 11, bài 11

-
I. Ghép các điện trở thành bộ 1. Ghép nối tiếp: $$ \left\{ \begin{matrix} U_{b}=U_1+U_2+...+U_n \\ I_b=I_1=I_2=...=I_n \\ R_b=R_1+R_2+...+R_n \end{matrix} \right. $$ 2. Ghép song song: $$\left\{\begin{matrix} U_{b}=U_1=U_2=...=U_n\\ I_b=I_1+I_2+...+I_n \\ \displaystyle\frac{1}{R_b}=\displaystyle\frac{1}{R_1}+\displaystyle\frac{1}{R_2}+...+\displaystyle\frac{1}{R_n} \end{matrix}\right.$$ II. Định luật Ohm đối với toàn mạch 1. $I=\displaystyle\frac{E}{R_N+r}$ $E=I\left ( R_N + r \right )$ $U_N=IR_N=E-Ir$ 2. $A_{ng}=EIt\Leftrightarrow P_{ng}=EI$ $A_{N}=UIt\Leftrightarrow P_N=UI$ Ngoài ra, $P=\displaystyle\frac{U^2}{R}=I^2R$ khi mạch ngoài chỉ chứa điện trở $R$. III. Ghép nguồn thành bộ 1. Bộ nguồn nối tiếp $$\left\{\begin{matrix} E_b=E_1+E_2+...+E_n \\ r_b=r_1+r_2+...+r_n \end{matrix}\right.$$ Nếu n nguồn giống nhau thì: $$\left\{\begin{matrix} E_b=nE_0 \\ r_b=nr_0 \end{matrix}\right.$$ 2. Bộ nguồn song song (*)$$\left\{\begin{matrix} E_b=E_0 \\ r_b=\displaystyle\frac{r_0}{n}...
Đọc thêm

Giải toán cho Trang

-
Hình ảnh
a) Góc $\widehat{ABC}=90^0$ nội tiếp chắn cung AC nên AC là đường kính. b) Áp dụng định lý Pitago cho tam giác ABC vuông tại B, ta có: $$AC=\sqrt{AB^2+BC^2}=\sqrt{5^2+12^2}=13.$$ $$\Rightarrow R=\frac{AC}{2}=\frac{13}{2}.$$ Ta có: $\widehat{DAE}=\widehat{DAH}+\widehat{HAE}=2\widehat{BAH}+2\widehat{HAC}=2\widehat{BAC}=180^0$ $\Rightarrow D, A, E$ thẳng hàng. Mà $\left\{\begin{matrix} AD=AH\\ AE=AH \end{matrix}\right.\Rightarrow AD=AE\Rightarrow $ A là trung điểm DE. Do đó, $DE^2=(2AH)^2=4AH^2$                                                                    $(1)$ Mặt khác, $\left\{\begin{matrix} BD=BH\\ CE=CH \end{matrix}\right.\Rightarrow 4.BD.CE=4.BH.CH=4AH^2$                $(2)$ Từ $(1)$ và $(2)$ suy ra $DE^2=4.BD.CE$ (đpcm) $$(d_1): (m+2)x-(2m-1)y+6m...
Đọc thêm