Lập lịch CPU
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Một CPU cần thực hiện $N$ tác vụ, mỗi tác vụ được ký hiệu bằng một chữ cái in hoa từ A đến Z (biểu diễn bởi xâu $S$ độ dài $N$). Mỗi đơn vị thời gian, CPU có thể thực hiện một tác vụ hoặc nghỉ (idle). Tuy nhiên, hai lần thực hiện cùng một loại tác vụ phải cách nhau ít nhất $K$ đơn vị thời gian nghỉ (tức là nếu chạy tác vụ loại X ở giây $t$, lần tiếp theo chạy X sớm nhất là giây $t + K + 1$). Hãy tìm tổng thời gian ít nhất để hoàn thành tất cả $N$ tác vụ.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N$ và $K$.
Dòng thứ hai chứa xâu $S$ gồm $N$ chữ cái in hoa (A–Z).
Dữ liệu ra
In ra tổng số đơn vị thời gian ít nhất.
Ví dụ
| Input | Output |
|---|---|
| 6 2 AAABBB |
8 |
| 6 0 AAABBB |
6 |
Giới hạn
- $1 \le N \le 10^5$.
- $0 \le K \le 100$.
Community Discussion