原题地址http://poj.org/problem?id=2915
题目大意：
经典的zuma游戏！给定一个长度不超过200的zuma序列, 规定大于等于M个同色珠子相碰就会自动消掉（2<=M<=20），要求射入最少的珠子（位置和颜色没有限制），消掉整个zuma序列。一个特殊条件：射入的珠子的颜色必须是其左右两侧珠子颜色之一。
算法：
先考虑一个比较简单的问题，COCI版zuma（出处2009~2010 contest #5）
COCI版zuma和2915版zuma的区别是，COCI版中当同色珠子达到M时，可以选择消去（也允许选择不消去，不像2915版zuma是自动消的）
这个问题用hym神犇在三省题解中的算法就行了：
dp[i,j,k]表示第i~j的珠子，附带k个和第j个珠子颜色相同的珠子，至少需要多少次射击才能全消
则当k<M-1时可以选择往最后补一个珠子，花费dp[i,j,k+1]+1步；当k=M-1时可以选择把最后一串消掉，花费dp[i,j-1,0]步
另外可以找到一个i<=L<j，使得第L个珠子颜色和第j个珠子颜色相同，然后消掉(L+1)~(j-1)这一段珠子，然后转化成dp[i,L,k+1],总代价为dp[i,L,k+1]+dp[L+1,j-1,0]
这个算法之所以正确，是因为我们可以选择消掉或不消掉已经达到M的珠子
如果同色珠子到达连续M个就自动爆炸的话，那么这个算法就是错误的了
例如这个数据
6 3
1 2 1 3 1 1
这时正确的方法应该是先用两个珠子消掉2，然后用两个珠子消掉3，然后1自爆，共计4个珠子
但用上面的算法就出错了，因为上面的算法认为如果要把第一个1和最后两个1连起来，必须把中间的’2 1 3’全部消掉。而不能处理先消’1 2 1’中的2，然后保留1，转而去消3的做法。
我们可以修改这个算法。
上面那个算法之所以出错，是因为有时候不应该过早的把珠子连成串消掉的。
首先把连续同色珠子合并，合并成二元组(cl,sz)表示颜色为cl，共计sz个的连续珠子。因为射入的珠子必须是其左右两侧珠子颜色之一，所以连续颜色块一定不会被拆散。（如果没有这个条件此题就不可做了，参考GYZ神犇的神文）
我们不妨把初始队列中大于等于M个的连续同色珠子视为M-1个，这样明显是不会改变结果的，但能为后期的处理带来很大的方便。
这时，我们发现，如果我们要攒肥了一起消，那么最多只能消掉2M-2个珠子（废话）。同时，碰撞的两段的每一段长度都小于M（废话）。
我们用zuma[i]表示第i个zuma二元组。
我们定义状态dp[i,j,k]表示想要消掉第i~j的珠子以及附带的k个和第j个珠子颜色相同的珠子，所需最少射击次数。但这里k的定义和hym神犇的定义有所区别
当k<m时，表示有k个自由珠子
当m<=k<2m时，表示已经配出了一段尽量长，但长度小于M的同色珠子，还有k-m个自由珠子可配
另外，这里的k并不一定是实际存在的连续珠子，而可以是一段序列经过一些操作后，可以达到k个连续珠子这个结果. 也就是说，如果k+zuma[j].sz>=M时并不一定引起消除，因为这时k还是一段安全的队列。我们可以先操作k产生自由珠子，然后操作zuma[j]使其和k中的自由珠子配起来，然后再操作k产生一段非自由的珠子，最后消掉间隔自由珠子和非自由珠子的那一段队列，从而引起消除。因此，只要条件允许，即使k+zuma[j].sz>=M我们依然可以扩展k。
对于状态dp[i,j,k]我们分情况讨论：
当i>j时，值为0
当i<=j时
转移1：可以把第j段以及附带的k个珠子强行全消掉，变成dp[i,j-1,0]
转移2：分情况讨论
情况1：zuma[j].sz+k<M. 这时，zuma[j]和k无论怎么处理都不会引起消除。转移和hym神犇的相同。为dp[i,L,k+zuma[j].sz]+dp[L+1,j-1,0]其中zuma[L].cl=zuma[j].cl
情况2：k<M但zuma[j].sz+k>=M. 这时，k不可以继续吸纳zuma[j]的珠子了，k这一段变成了非自由的序列。zuma[j]变成新的自由珠子。转移为dp[i,L,M+zuma[j].sz]+dp[L+1,j-1,0]其中zuma[L].cl=zuma[j].cl
情况3：k>=M且zuma[j].sz+K<2M-1. 这时，和情况1一样。只是多了一段非自由的珠子。不用管它，因为我们转移只需要考虑自由珠子。转移为dp[i,L,k+zuma[j].sz]+dp[L+1,j-1,0]其中zuma[L].cl=zuma[j].cl
情况4：zuma[j].sz+k>=2M-1. 这时，zuma[j]不可能参与到k的消除中去，因为如果两段序列如总长度能达到2M-1则必然其中一段序列长度会达到M从而引起消除。所以zuma[j]根本不可能参与到k的消除中去。k只能自己消除，zuma[j]变成新的自由珠子。所以转移为dp[i,L,zuma[j].sz]+dp[L+1,j-1,0]其中zuma[L].cl=zuma[j].cl（注意4个方程的细小区别）
这样就可以了。时间复杂度O(N^3*M). 不要用记忆化搜索，否则会tle。