Overseer of Pearls, orchestrating the chain of vanishing beads in silent space.
在埃尔德莫尔的暮色中,古老的修道院静默伫立,雪花轻舞在橡树的枝头。
多年前,一位高贵的少女与来自遥远海岸的旅行商人相遇。商人向她展示了一款游戏。对于出生在
少女被游戏的美丽深深吸引,决定用智慧解开其奥秘。时过境迁,她在修道院中深入研究,发现游戏远比想象复杂。她最初直观的办法未能奏效,迫使她不断思考更加巧妙的策略。
如今,这道祖玛的谜题传递到你的手中。记住少女的经历——看似简单的表象下隐藏着需要深刻理解的复杂性。以坚定的决心迎接挑战,愿你的旅程如埃尔德莫尔雪覆的树木一般坚韧。
题目描述
在这款游戏中,初始局面有
在一次操作中,你可以在序列中的任何位置插入一颗质量为
插入这颗珠子以后,将发生如下的消除过程:
立即消除:如果插入的珠子与其左右至少一个相邻的珠子颜色相同,并且该颜色极长的珠子连续段(包括刚插入的珠子)的质量总和
,则整个同色连续段将被消除。消除以后,左右两侧的珠子将相撞,把左右两个序列合并到一起。连锁反应:当左右两颗珠子相撞时:
- 如果两颗珠子颜色相同,并且两个同色连续段的质量总和相加
,则两个连续段将同时被消除。 - 消除以后,可能会导致新的珠子相撞,继而触发更进一步的消除。
连锁反应将这样一步步的发生,直到相撞的两颗珠子颜色不同,或者颜色相同但是两个同色连续段的质量总和相加
,此时连锁反应停止。- 如果两颗珠子颜色相同,并且两个同色连续段的质量总和相加
游戏的目标是消除整个序列中的所有珠子,请你编写程序计算出需要的最小操作次数
输入格式
第一行五个正整数
第二行
第三行
输出格式
只需要输出一行一个正整数
样例零
input
11 10 4 4 3 1 1 2 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1
output
6
explanation
在下文中我们用 [x] 表示插入一颗颜色为
1 1 2 1 1 3 4 1 1 1 1 1 2 1 1 3 4 1 [2] 1 1 1 1 2 1 1 3 4 1 2 1 1 1 1 2 1 1 3 [3] 4 1 2 1 1 1 1 2 1 1 3 3 4 1 2 1 1 1 1 2 1 1 3 3 [3] 4 1 2 1 1 1 1 2 1 1 >!< 4 1 2 1 1 1 1 2 1 1 4 1 2 1 1 1 1 2 1 1 4 [4] 1 2 1 1 1 1 2 1 1 4 4 1 2 1 1 1 1 2 1 1 4 4 [4] 1 2 1 1 1 1 2 1 1 >!< 1 2 1 1 1 1 2 >!< 2 1 1 1 1 2 2 1 1 1 1 2 2 [2] 1 1 1 1 >!< 1 1 >!< win
样例一~十五
见附件下载,它们分别对应子任务
限制与约定
对于所有数据,保证
保证
子任务编号 | 子任务分值 | 特殊性质 | 子任务依赖 | |||
---|---|---|---|---|---|---|
无 | 无 | |||||
无 | ||||||
无 | ||||||
保证所有 |
无 | |||||
保证数据随机生成 | 无 | |||||
保证答案 |
无 | |||||
无 | 无 | |||||
子任务
- 保证
。 - 从一个
的空序列开始。 - 每次在
中等概率随机一个整数 ,然后在 中等概率随机一个整数 。 - 如果把
添加到序列的末尾之后仍有 ,那么就添加。 - 直到
时停止。
保证子任务
时间限制:
空间限制:
请你注意:对于赛后添加的 hack 数据,我们只会检查