首页 > 试题广场 >

小美的代金券要过期啦

[编程题]小美的代金券要过期啦

外卖节即将过去了，小美还有很代金券没有消费掉，美团面向小美这样的用户推出了一个新的活动，即代金券消消乐活动。系统会把小美的代金券打乱顺序排成一排，小美可以进行任意多次如下操作：

如果存在相邻的两个代金券金额相等,设其面额为x，小美可以使用这两张代金券换一张面额为x+1的代金券，并将其仍放在原来两张券的位置上，每进行一次这样的操作，小美就可以获得1元可以无限期使用的奖励金。

小美觉得奖励金可太香了，因此她想获得尽可能多的奖励金，请问她最多可以获得多少奖励金。

输入第一行仅包含一个正整数n，表示小美拥有的代金券数量。(1<=n<=500)
输入第二行包含n个正整数，每个整数x表示一张代金券的面额，同时这也是系统排出的代金券顺序。(1<=x<=100)

输出仅包含一个整数，表示小美最多可以获得的奖励金数量。

示例1

输入

5
1 1 1 1 1

{1,1,1,1,1}->{1,1,1,2}->{1,2,2}->{1,3}

算法知识视频讲解

暂无题解

C++工程师 iOS工程师安卓工程师美团前端工程师算法工程师 2021 大数据开发工程师 Java工程师

上传者：小小

难度：

51条回答 65收藏 5515浏览

扫一扫，把题目装进口袋