有几天没有写博客了，主要原因就是csdn新推出来的OJ系统对c#支持的不太好，所以没有把最新的题的解题思路放上来，今天就把那个彩色石头的题写下思路。
有一行彩色的棋子，每个棋子的颜色是k种颜色之一。你不能改变棋子的顺序，但是可以移走一些棋子。问至少移走多少个石子，才能使得两个同色得石子之间没有其他颜色的棋子？
输入格式：
多组数据，每组数据两行，第一行是两个整数n和k, 1<=n<=100, 1<=k<=5
下一行是n个在[1..k]范围内的正整数，代表每个棋子的颜色。
输出格式：
每组测试数据输出一行包含一个整数，表示至少移走的石子数。
注：可以移走第2个第7个棋子。
输入样例
10 3
2 1 2 2 1 1 3 1 3 3
输出样例：
2
解题思路：
这道题应该说是一个比较典型的动态规划和状态压缩的题了。所以，我们考虑这个这道题的解题思路的时候，就要考虑，对于已经分析好的K个石头，增加一个石头K+1的时候，如何处理这个石头的问题。
因此，要分析两部分，
第一部分：处理好的K个石头，应该得到什么？
第二部分：第K+1个石头，怎么处理？
先看第一部分的分析：处理好的K个石头，应该得到什么？
最终结果应该是每种颜色石头都在一起，先不考虑最后的结果，那么这一定是一个结果集，那么最少的那种形式，一定是其中的一个（可能多个），即：A...AB....BC....C......
A表示某一个编号，B表示....C表示....................
比如说：1,2,1,2
我们得到的结果集：只有{(1),(2),(12),(2,1)}这4种形式
即得到1的这种形式，要把2全部划掉，需要划掉2个
要得到1,2这种形式，要把第三个1划掉，即1,2,2，需要划掉1个
。。。。
。。。。
然后从这个集合中找到划掉最少的，那么就是我们要得到的答案。
再看第二部分：第K+1个石头的处理
1、当Stone[k+1]==集合中某一项最后一个的颜色，那么这种形式的就不用划掉
2、当Stone[k+1] !=集合中某一项最后一个的颜色，那么我就要考虑这种形式里面出现过这种颜色的石头没有
2.1 出现过，那么要保持这种形式，这个石头就必须划掉
2.2 如果没有出现过，那么，就会考虑增加一种新的形式，同时，当前这种形式要保持，就必须划掉这个石头
还是举例来说吧：
例如，1,2,1,2
我们到的集合是：
集合状态---------需要划掉的石子数
1--------------------2
2--------------------2
1,2-----------------1
2,1-----------------2
当新增加了一个石子，2，变成了1,2,1,2,2
那么遍历上面的集合
对于1，属于）2---2.2里面说的情况，因为集合中已经有1,2这种形式，所以不用增加，所以结果是：1-------3
对于2，属于）1里面说的情况，因此不用变，2---------2
对于1,2，也属于）1，不变，1,2----------1
对于2,1，属于）2.----2.1情况，所以要划掉，结果为：2，1-------------------3
最后的结果集为：
集合状态---------需要划掉的石子数
1--------------------3
2--------------------2
1,2-----------------1
2,1-----------------3
遍历这个结果集，就知道，对于1,2,1,2,2，我们找到了1,2这种形式，只需要划掉一个石子就可以满足，这是最少的。
以后每增加一个石子，都按照上述逻辑处理，直到所有石子处理完毕，我们到结果集中查找划掉石子数最少的，就是我们要得到的结果。
最后用随机数据进行测试，100位，5种颜色，平均计算时间都在0.03秒一下，由于csdn的OJ现在还是不能提交c#，所以，只把思路贴出来。
彩色石子-c#求解-英雄会在线编程题目,布布扣,bubuko.com
原文：http://blog.csdn.net/mamihong/article/details/22752217
