← 返回题目列表

Codeforces · 802/A1

A1. 海蒂和图书馆(简单)

中文机器翻译题面 查看原题

你对海蒂的搜索已经结束——你终于在图书馆找到了她,她打扮得像人类。事实上,她在那里度过了很长时间,现在她正在经营这个地方!她的工作是购买书籍并将其存放在图书馆,以便人们可以借阅和阅读。有 $$$n$$$ 不同的书,编号为 $$$1$$$ 到 $$$n$$$。

我们将关注连续 $$$n$$$ 天内图书馆的运营情况。海蒂事先知道,在第 $$$i$$$ 天 ($$$1 \le i \le n$$$) 恰好有一个人会来到图书馆,请求借阅这本书 $$$a_i$$$,在几个小时内读完,并在当天晚些时候归还这本书。

海蒂非常想取悦她所有的客人,因此她将确保在第 $$$i$$$ 日的图书馆里始终有这本书 $$$a_i$$$ 可用。在第 $$$i$$$ 天的前一天晚上,她可以选择去书店(书店在晚上营业,以避免与图书馆竞争)并以 1 瑞士法郎的价格购买任何书籍。当然,如果她已经在图书馆有书了,她就不需要再买了。最初,图书馆没有书籍。

但有一个问题。图书馆的容量为 $$$k$$$ – 这意味着在任何时候,图书馆最多可以有 $$$k$$$ 本书。如果购买一本新书会导致 Heidi 拥有超过 $$$k$$$ 的书,那么她必须首先扔掉她已经拥有的一些书,以便为新书腾出空间。如果她以后需要一本她扔掉的书,她将需要再次购买那本书。

给你 $$$k$$$ 和书籍请求序列 $$$a_1, a_2, \ldots, a_n$$$。满足所有要求购买新书的最低成本是多少(瑞士法郎)?

输入

输入的第一行将包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 80$$$)。第二行将包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) – 图书请求的序列。

输出

在一行中打印在商店购买书籍的最低费用,以满足所有要求。

示例

输入
复制

4 80
1 2 2 1

输出
复制

2

输入
复制

4 1
1 2 2 1

输出
复制

3

输入
复制

4 2
1 2 3 1

输出
复制

3

注意

在第一个测试用例中,海蒂能够永远保留所有书籍。因此,她只需要在第一天之前购买$$$1$$$的书,在第二天之前购买$$$2$$$的书。

在第二个测试用例中,她一次只能保留一本书。因此她需要在第一天、第二天和第四天购买新书。

在第三个测试用例中,在第三天购买 $$$3$$$ 书之前,她必须决定应该扔掉 $$$1$$$ 和 $$$2$$$ 中的哪本书。当然,她应该保留这本书$$$1$$$,第四天会要求提供。