传送门：http://poj.org/problem?id=2915
题意：给定一串珠子(个数<=200,种类<=26)和一个数字M(2<=M<=20)，你有无限个各种颜色的珠子，根据祖玛的规则(每M个同色珠子连在一起会消去)用最少的珠子消去所有珠子，输出最少需要的珠子数.
注意：
1、起始状态可能有些同色珠子长度已超过M，你仍需要加入一个珠子，或者从左右引入珠子将其消去
2、每次插入的珠子必须与左边或右边珠子颜色相同
思考过程：
比较直觉地会想到区间dp，前两维l,r应该是区间左右端点，但是状态的构造是一个难点。注意到每M个同色珠子连在一起会消去，所以连续的珠子未必越多越好，但由于珠子合并的时候必然是两两之间顺序合并，所以珠子可以分作两个状态：单串连续和两串分别连续，再多就没有意义了。我们先将连续的珠子合并在一起，用一个结构体A表示，A.num表示珠子数量，A.col表示珠子颜色，注意到由于初始超过M个珠子也不能自动消去，我们将所有>=M的num设为M-1，后面会看到这样处理的好处。
我们用dp[l][r][k][0]表示清除以l，r为左右端点，且r后面跟了k个连续珠子的区间时所需最小珠子数；dp[l][r][k][1]表示清除以l，r为左右端点，且r后面跟了两串分别连续的珠子(可以看做尚未合并，但可以以零代价合并的两串珠子，且两串珠子数量大于等于M，较近的一串有k个，“且这两个分别连续的串要同时消去”)时所需的最小珠子数。而在dp顺序上，我们选择让“中间的珠子被清空后，右边的珠子向左边移动”
转移方程(O(M*N3))：
一、对于dp[l][r][k][0]:
1、来自dp[l][r-1][0][0]+max(0,M-A[r].num-k)，表示暴力清除第r位及后面区间(此时可以看到，之前取M-1的操作省去了对k==0 && A.num>=M时的讨论)
2、A[r].num+k<M时，来自dp[l][x][A[r].num+k][0]+dp[x+1][r-1][0][0]，其中A[x].col==A[r].col，l<=x<r，表示清除x+1~r-1区间后，再让x继承r及此后珠子，再进行清除的代价
3、A[r].num+k>=M，来自dp[l][x][k][1]+dp[x+1][r-1][0][0]，其中A[x].col==A[r].col，l<=x<r，表示清除x+1~r-1区间的代价加上让x继承两个个零代价合并串后的区间清除的代价
二、对于dp[l][r][k][1]:
1、来自dp[l][r-1][0][0]+暴力清除代价——若k+A[r].num<M，则暴力清除代价为0，否则暴力清除代价为max(0,M-A[r].num)(让后面两个零代价合并串先行合并)。这里会产生一个小问题，是否让r与较近的串先合并，然后保留较远的串会较好？但操作上做不到，首先我们并没有保存后面串长，而且这样的操作会产生问题——后面两串可以零合并的前提是消去中间区间的代价我们已经加到dp数组中(见一3)，但一旦让中间区间与r-1接触，其消去代价可能发生变化（变大变小皆有可能）。再仔细思考一下，我们并不需要这么做，因为在dp的时候，我们已经考虑到了这两串分别消去的状态，所以dp[l]][r][k][1]的说明中再加一句“且这两个分别连续的串要同时消去”会更准确
2、A[r].num+k<M-1,来自dp[l][x][A[r].num+k][1]+dp[x+1][r-1][0][0]，其中A[x].col==A[r].col，l<=x<r，意思和上面差不多，至于<M-1,而非<M的原因是根据定义，做消去的时机不会比M-1更晚（可以稍微考虑下），当然调整为M也不会错
3、A[r].num+k>=M-1，来自dp[l][x][A[r].num][1]+dp[x+1][r-1][0][0]，其中A[x].col==A[r].col，l<=x<r
细节：
1、最好不要和我一开始一样试图写记忆化搜索，系统栈的速度emmmmmmmmmmm
2、提前开个预处理数组，在寻找使得A[x].col==A[r].col的x时实现一步跳转
3、常数别写的太大了