304188: CF802A. Heidi and Library (easy)
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Heidi and Library (easy)
题意翻译
Heidi有一个图书馆。她同时知道，在时间 i，会有一个人来借第$a_i$书，同时在当天把书还回来。她可以在借书的前一天晚上买书，花费1元。 有的$a_i$会是相同的数字，表示有的书会有人在不同的天借阅。 她的图书馆多只能装$k$本书，所以当她的存书超过$k$，他就要把多余的书扔掉。一本书扔掉后，如果有人借，他就需要花费1元重新购买。 给定所有将来的$i$和$a_i$，请问Heidi少需要多少钱，才能满足所有人的借书需要？ 最开始Heidi的图书馆是没有书的~~（新开张的图书馆？）~~ 输入包括两行： 第1行有两个数n，k表示一共有n天，Heidi的图书馆容量为k 第2行包括n个数，第i个数表示在第i天会有一个人借书a[i] 输出仅一个数： 即Heidi在最少需要多少钱 数据范围 $\left(1 <=n,k<=80\right)$ $\left(1 <=a_i<=n\right)$题目描述
Your search for Heidi is over – you finally found her at a library, dressed up as a human. In fact, she has spent so much time there that she now runs the place! Her job is to buy books and keep them at the library so that people can borrow and read them. There are $ n $ different books, numbered $ 1 $ through $ n $ . We will look at the library's operation during $ n $ consecutive days. Heidi knows in advance that on the $ i $ -th day ( $ 1<=i<=n $ ) precisely one person will come to the library, request to borrow the book $ a_{i} $ , read it in a few hours, and return the book later on the same day. Heidi desperately wants to please all her guests, so she will make sure to always have the book $ a_{i} $ available in the library on the $ i $ -th day. During the night before the $ i $ -th day, she has the option of going to the bookstore (which operates at nights to avoid competition with the library) and buying any book for the price of 1 CHF. Of course, if she already has a book at the library, she does not need to buy it again. Initially, the library contains no books. There is a problem, though. The capacity of the library is $ k $ – this means that at any time, there can be at most $ k $ books at the library. If buying a new book would cause Heidi to have more than $ k $ books, she must first get rid of some book that she already has, in order to make room for the new book. If she later needs a book that she got rid of, she will need to buy that book again. You are given $ k $ and the sequence of requests for books $ a_{1},a_{2},...,a_{n} $ . What is the minimum cost (in CHF) of buying new books to satisfy all the requests?输入输出格式
输入格式
The first line of input will contain two integers $ n $ and $ k $ ( $ 1<=n,k<=80 $ ). The second line will contain $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=n $ ) – the sequence of book requests.
输出格式
On a single line print the minimum cost of buying books at the store so as to satisfy all requests.
输入输出样例
输入样例 #1
4 80
1 2 2 1
输出样例 #1
2
输入样例 #2
4 1
1 2 2 1
输出样例 #2
3
输入样例 #3
4 2
1 2 3 1
输出样例 #3
3