Trạm Bưu Điện Dọc Đường
Đề bài
Trên một con đường thẳng có $N$ ngôi làng nằm ở các tọa độ tăng dần $x_1 < x_2 < \dots < x_N$. Chính quyền muốn xây dựng đúng $K$ trạm bưu điện tại một số ngôi làng sao cho tổng khoảng cách từ mỗi ngôi làng đến trạm bưu điện gần nhất là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le K \le N \le 10000, K \le 20$).
- Dòng thứ hai chứa $N$ số nguyên $x_1, x_2, \dots, x_N$ ($0 \le x_1 < x_2 < \dots < x_N \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng khoảng cách nhỏ nhất có thể.
Ví dụ
Đề bài
Cho ba xâu ký tự $A$, $B$ và $C$ chỉ gồm các chữ cái tiếng Anh in thường. Xâu $C$ được gọi là xâu đan xen của $A$ và $B$ nếu có thể phân hoạch các ký tự của $C$ thành hai dãy con không giao nhau sao cho dãy thứ nhất tạo thành $A$ và dãy thứ hai tạo thành $B$ (giữ nguyên thứ tự).
Cấu trúc con tối ưu: $dp[i][j]$ cho biết $i$ ký tự đầu của $A$ và $j$ ký tự đầu của $B$ có thể đan xen thành $i+j$ ký tự đầu của $C$ hay không.
Dữ liệu vào
Ba dòng lần lượt chứa các xâu $A$, $B$ và $C$.
Dữ liệu ra
In ra YES nếu $C$ là xâu đan xen của $A$ và $B$, ngược lại in ra NO.
Ví dụ
Input
Giới hạn
|
|---|
Community Discussion