8576: BZOJ4576:[Usaco2016 Open]262144

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

262144 (262144) Description Bessie喜欢在她的手机上下载游戏玩,尽管她发现她的大蹄使用小触摸屏幕相当麻烦。她特别感兴趣的是她正在玩 的游戏。 游戏从一个有N个正整数的序列开始(2≤N≤262,144),每个数字在1...40的范围内。 在一个步骤中, Bessie可以获取具有相等值的两个相邻数字,并且用比这两个数大一的值替换这两个数值(例如,她可以用8替换 两个相邻的7)。目标是在游戏结束时最大化在序列中存在的最大数字的值。 请帮助Bessie得分尽可能高! 题目大意: 给定一个长度为n(n<=2^18)的序列,初始元素值为1到40之间的整数,每次操作可以将两个相邻的并且大小相同 的正整数替换成一个比原数大一的正整数。要求最大化最终数列中的最大值。


输入格式

第一行输入包含N,接下来的N行在游戏开始时给出N个数字的序列。


输出格式

请输出可以生成的最大整数。


样例输入

4
1
1
1
2

样例输出

3
//在所示的示例中,Bessie首先合并第二和第三个1以获得序列1 2 2,然后她将两个2合并成3. 注意,合并前两个1不是最佳的。

提示

没有写明提示


题目来源

Platinum 鸣谢g1n0st提供译文

加入题单

上一题 下一题 算法标签: