Trạm Bưu Điện Dọc Đường

Buổi 38 — Divide & Conquer DP Dynamic Programming
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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
Input Output
6 2
1 2 3 6 7 9
5
5 1
1 4 6 8 10
13 Output
aabcc
dbbca
aadbbcbcac
YES
aabcc
dbbca
aadbbbaccc
NO
Giới hạn
  • $1 \le N \le 10000$
  • $1 \le K \le \min(N, 20)$
  • $0 \le x_i \le 10^9$
Draft saved