Galindo đi Việt Nam
Xem PDFgalindo.md
Sau một thời gian gieo rắc nỗi sợ ra toàn thế giới nhưng lại bị lôi ra làm trò đùa ở Việt Nam. Jonathan Galindo quyết định đến đây để xem con người ở đây như thế nào. Ở đây anh bị choáng ngợp, thu hút bởi những điệu múa quạt của anh Bảnh, những tiết dạy làm người của thầy Huấn, những điệu nhảy sexy của Trần Đức Bo hay là bác Trần Tiger cầm súng bắn chết mấy thằng chửi thề. Vì quá yêu mến đất nước Việt Nam nên Jonathan Galindo quyết định giúp đất nước Việt Nam sánh vai với các cường quốc năm châu. Nhưng để làm được điều đó thì Galindo phải giải được 1 bài toán mà thánh coder cũng đồng thời là người đẹp trai top 7 tỉ thế giới đưa ra. Bạn hãy giúp Galindo giải bài toán nhé !
Bạn được đưa ra một mảng số nguyên \(a_1,..., a_n (1 \leq a_i \leq n)\). Mức độ “To và tròn” của một đoạn con liên tiếp là số cặp các phần tử bằng nhau của đoạn đó. Hãy chia dãy thành \(k\) đoạn con không trống để tổng mức độ “To và tròn” của các đoạn con là nhỏ nhất có thể (Vì bin9638 thích “Lép và phẳng”).
Input
- Dòng đầu chứa 2 số nguyên \(n, k (2 \leq n \leq 10^5, 2 \leq k \leq min (n, 20))\)
- Dòng tiếp theo chứa dãy \(a_1, a_2, ..., a_n (1 \leq a_i \leq n)\).
Output
- Một dòng duy nhất là mức độ “To và tròn” tối thiểu.
Scoring
- Subtask \(1\) (\(1\%\) số điểm): \(n=10\)
- Subtask \(2\) (\(49\%\) số điểm): \(n \leq 1000\)
- Subtask \(3\) (\(48\%\) số điểm): \(n<10^5\)
- Subtask \(4\) (\(1\%\) số điểm): \(n=10^5\)
- Subtask \(5\) (\(1\%\) số điểm): không ràng buộc gì thêm
Example
Test 1
Input
7 3
1 1 3 3 3 2 1 Output
1Test 2
Input
13 3
1 2 2 2 1 2 1 1 1 2 2 1 1 Output
9Note
- Ở test 1 \([1], [1, 3], [3, 3, 2, 1]\) là cách chia.
- ở test 2 \([1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]\) là cách chia.
Bình luận
khó
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Galindo đọc xong đề bài thì khóc thét 🙂
Hic giờ mới được duyệt @@
bin9638 :))
bin9638 dâm tặc =))
ở test 1 chia kiểu [1,3] [1,3] [3,2,1] ko được hay sao ?
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.