问题 2136. -- 青蛙王子玩zuma游戏

2136: 青蛙王子玩zuma游戏

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 2
[提交][状态][讨论版]

题目描述

青蛙们正遭遇一次史无前例的危机!为了解救族人,青蛙王子必须完成一个古老而艰难的游戏——zuma游戏。
zuma游戏中,一条通道中有一些玻璃珠,每个珠子有各自的颜色,如图1所示。青蛙王子可以做的是选择一种颜色的珠子射入某个位置。


    图2中青蛙王子选择一颗蓝色珠子,射入图示的位置,于是得到一个图3的局面。



    当青蛙王子射入一颗珠子后,如果射入的珠子与其他珠子组成了三颗以上连续相同颜色的珠子,这些珠子就会消失。例如,将一颗白色珠子射入图4中的位置,就会产生三颗颜色相同的白色珠子。这三颗珠子就会消失,于是得到图5的局面。



需要注意的一点是,图4中的三颗连续的黄色珠子不会消失,因为并没有珠子射入其中。

    珠子的消失还会产生连锁反应。当一串连续相同颜色的珠子消失后,如果消失位置左右的珠子颜色相同,并且长度大于2,则可以继续消失。例如,图6中,射入一颗红色珠子后,产生了三颗连续的红色珠子。当红色珠子消失后,它左右都是白色的珠子,并且一共有四颗,于是白色珠子也消失了。之后,消失位置的左右都是蓝色珠子,共有三颗,于是蓝色珠子也消失。最终得到图7的状态。注意,图7中的三颗黄色珠子不会消失,因为蓝色珠子消失的位置一边是紫色珠子,另一边是黄色珠子,颜色不同。


    除了上述的情况,没有其他的方法可以消去珠子。

    现在,请你协助青蛙王子消除通道中的珠子。给出每一轮选择的珠子的颜色、射入的位置,请你计算出最后还剩下多少颗珠子。

输入

第一行两个正整数n, m,分别表示珠子的个数和游戏进行的轮数。(1<=n,m<=200)
第二行n个用空格隔开的正整数a[i]。每个正整数表示开始时通道中一颗珠子的颜色。
接下来m行,每行两个正整数c, x,表示将一颗颜色为c的珠子射在从左往右第x颗珠子的右边。若x=0则表示射在第一颗珠子的左边。注意珠子的编号从1开始,第一颗珠子编号为1,第n颗珠子编号为n。

输出

输出一行一个整数,表示最后剩下的珠子的个数。

样例输入

8 3
1 2 2 1 3 3 1 1
2 1
3 2
1 0

样例输出

1

提示

样例解释:以下用括号表示射入珠子的位置:
第一轮:1 (2) 2 2 1 3 3 1 1 消去后:1 1 3 3 1 1
第二轮:1 1 (3) 3 3 1 1 消去后:
第三轮:(1) 消去后:1

来源

[提交][状态]