#D. (2023年小学组/初中组区赛第四题)方块消除

    传统题 1000ms 256MiB

(2023年小学组/初中组区赛第四题)方块消除

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

方块消除

题目描述

小S在玩俄罗斯方块消消乐,只需要将相同颜色的方块放在一起便能消除,每局游戏根据消除相邻相同颜色的最大数量得到积分 , 每消除一个方块会得到1分。小S由于精通计算机原理,便决定通过作弊来让自己得到更高的分数,在一开始给定的局面,所有的方块并排放成一行,游戏开始的时候相邻相同颜色的同时消除,并根据相邻相同颜色的最大数量得到积分。 例如 1 2 1 1 1 2 1 1 消除可以得到三分,因为相邻的1最多有三个。

Note : 积分的计算是只考虑最大的相邻相同颜色积木的数量,如果有多个,只考虑最大的而不能累计。

小S可以将最多k个方块在开局之前先全部删除,那么请你帮助他计算一下,他最多能得到多少积分?

输入描述

第一行输入三个正整数n,m,kn,m,k,分别表示长度为n的数组,共有m种不同的颜色,最多可以删除k个方块。

第二行输入n个正整数,代表每个方块的颜色。

输出描述

输出一个整数,代表最大得到的积分。

样例描述

输入1

10 3 2
1 2 1 1 3 2 1 1 2 2

输出1

4

可以考虑删除5位置处的3和6位置处的2

序列变为{1,2,1,1,1,1,2,2} 相邻的有四个连续1,积分为4

输入2

10 2 2
1 2 1 2 1 1 2 1 1 2

输出2

5

输入3

3 1 2
1 1 1

输出3

3

数据范围描述

对于10%的数据保证,nkn \le k

对于40%的数据保证,n,m,k2000n,m,k\le 2000

对于100%的数据保证,n,m,k107n,m,k \le 10^7

2023年 市北区区赛 - 初中组补题场

未认领
状态
已结束
题目
4
开始时间
2023-5-12 0:00
截止时间
2023-6-30 23:59
可延期
24 小时