UOJ Logo Universal Online Judge

UOJ

#941. 珍珠守卫

附件下载 统计

Overseer of Pearls, orchestrating the chain of vanishing beads in silent space.

在埃尔德莫尔的暮色中,古老的修道院静默伫立,雪花轻舞在橡树的枝头。

多年前,一位高贵的少女与来自遥远海岸的旅行商人相遇。商人向她展示了一款游戏。对于出生在 21 世纪的大家,可以看成祖玛的简化版。

少女被游戏的美丽深深吸引,决定用智慧解开其奥秘。时过境迁,她在修道院中深入研究,发现游戏远比想象复杂。她最初直观的办法未能奏效,迫使她不断思考更加巧妙的策略。

如今,这道祖玛的谜题传递到你的手中。记住少女的经历——看似简单的表象下隐藏着需要深刻理解的复杂性。以坚定的决心迎接挑战,愿你的旅程如埃尔德莫尔雪覆的树木一般坚韧。

题目描述

在这款游戏中,初始局面有 n 颗珠子从左到右排成一个序列。其中的第 i 颗珠子具有颜色 ai{1,2,,m} 和质量 ci{1,2,,k1},正整数 m,k2 分别表示 不同颜色的个数游戏的消除阈值

在一次操作中,你可以在序列中的任何位置插入一颗质量为 1 的珠子(颜色自选),包括在第一颗珠子之前以及最后一颗珠子之后。

插入这颗珠子以后,将发生如下的消除过程:

  1. 立即消除:如果插入的珠子与其左右至少一个相邻的珠子颜色相同,并且该颜色极长的珠子连续段(包括刚插入的珠子)的质量总和 k,则整个同色连续段将被消除。消除以后,左右两侧的珠子将相撞,把左右两个序列合并到一起。

  2. 连锁反应:当左右两颗珠子相撞时:

    • 如果两颗珠子颜色相同,并且两个同色连续段的质量总和相加 k,则两个连续段将同时被消除。
    • 消除以后,可能会导致新的珠子相撞,继而触发更进一步的消除。

    连锁反应将这样一步步的发生,直到相撞的两颗珠子颜色不同,或者颜色相同但是两个同色连续段的质量总和相加 <k,此时连锁反应停止。

游戏的目标是消除整个序列中的所有珠子,请你编写程序计算出需要的最小操作次数 q

输入格式

第一行五个正整数 type,n,e,m,k,分别表示这个测试点属于子任务 type,初始局面的珠子个数,满足 ai=ai+1 的下标 i 的个数(初始局面中相邻同色的珠子对个数),不同颜色的个数和游戏的消除阈值。

第二行 n 个正整数 a1,a2,,an,表示初始局面 n 颗珠子的颜色。

第三行 n 个正整数 c1,c2,,cn,表示初始局面 n 颗珠子的质量。

输出格式

只需要输出一行一个正整数 q,表示消除整个序列需要的最小操作次数。

样例零

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] 表示插入一颗颜色为 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

样例一~十五

见附件下载,它们分别对应子任务 115

限制与约定

对于所有数据,保证 1n+e1202m,k51aim1cik1

保证 1mm 个颜色在最初的序列中都出现过至少一次,并且 m 个颜色在序列中第一次出现的位置 p1<p2<<pm

子任务编号 子任务分值 n+e m k 特殊性质 子任务依赖
1 1 120 2 2
2 9 5 2 1
3 9 2 5 1
4 15 5 5 保证所有 aiai+1
5 6 5 5 保证数据随机生成
6 6 20 5 5 保证答案 (n+e)/5
7 40 6
8 60 67
9 90 68
10 120 69
11 6 20 5 5
12 40 11
13 60 1112
14 90 1113
15 120 114

子任务 5 的保证数据随机生成指的是:

  • 保证 m=k=5
  • 从一个 n=e=0 的空序列开始。
  • 每次在 {1,2,,m} 中等概率随机一个整数 ai,然后在 {1,2,,k1} 中等概率随机一个整数 ci
  • 如果把 (ai,ci) 添加到序列的末尾之后仍有 n+e120,那么就添加。
  • 直到 n+e=120 时停止。

保证子任务 5 的数据恰好有 5 组,并且我们生成出来 5 组数据以后没有经过任何筛选。

时间限制:10.5s

空间限制:2GB

请你注意:对于赛后添加的 hack 数据,我们只会检查 type[1,15],不会检查这个测试点是否满足子任务 type 的限制。