Phân Hoạch Đa Dạng
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề bài
Cho dãy số nguyên $A$ gồm $N$ phần tử và số nguyên dương $K$ ($K \le N$).
Bạn cần chia dãy $A$ thành đúng $K$ đoạn con liên tiếp khác rỗng sao cho mỗi phần tử thuộc đúng một đoạn. Giá trị của một đoạn con là số lượng giá trị phân biệt có trong đoạn con đó.
Hãy tìm tổng giá trị lớn nhất của $K$ đoạn con.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên dương $N$ và $K$. Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
Dữ liệu ra
In ra một số nguyên duy nhất là tổng số phần tử phân biệt lớn nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 4 2 1 2 1 2 |
4 |
| 7 3 1 2 1 3 2 1 3 |
7 |
Giới hạn
- $1 \le K \le N \le 3 \cdot 10^4$
- $1 \le K \le 50$
- $1 \le A_i \le N$
Community Discussion