Phân Hoạch Đa Dạng

Buổi 39 — DP + Data Structures Dynamic Programming
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved