2006年百度之星程序设计大赛复赛题目4：彩球游戏
彩球游戏X博士是一个研究儿童智力开发方法的科学家，他为幼儿教育领域做出了许多贡献。最近，X博士正在研究一种适合儿童的游戏，用以辅助发展儿童的观察力、注意力和思维能力。经过连日的构思，X博士终于设计出了一种游戏：彩球游戏。彩球游戏是一种单人参与的游戏，游戏首先给出一串由许多不同颜色的小球组成的小球序列，以及一个整数参数M（M≥2）。一段连续的具有相同颜色的小球序列称为连续同色序列。小孩，即游戏参与者，每次可以向任意一段连续同色序列插入一个同色小球，使该序列的长度加一。当一段连续同色序列在插入一个同色小球后其长度达到M时，该序列就会爆炸消失，然后原序列两边的其余小球会重新连成一串，如果两段相同颜色的连续同色序列在此时连接在一起，它们就会合并形成一段新的连续同色序列。如果新形成的连续同色序列长度达到M，这段序列也会爆炸消失，然后重复上述过程，直到没有新的长度达到M的连续同色序列出现为止。游戏的目标很简单，就是插入尽量少的小球，使得所有小球都爆炸消失掉。通过长时间的游戏和不断提高游戏水平，这个游戏可以很好地开发儿童的观察力、注意力和思维能力。但是X博士仍然面临着一个困难的问题，他还需要设计出一个游戏演示AI程序，可以以最优的方式（即插入的小球数量最小）进行游戏，用于游戏教学，或者在游戏中对小孩给出提示。X博士并不擅长此类程序，因而他无法完成这个任务，你可以帮助他吗？输入格式：输入文件包含多组测试数据。每组测试数据第一行为整数M（2≤M≤20），第二行为一条非空的字符串，由大写字母组成且长度不超过200，表示初始的一串小球，不同的字母表示不同的小球颜色。初始时可能会存在一些长度达到M的连续同色序列，但这些序列不会马上爆炸消失。输出格式：每组测试数据输出一行，表示至少需要插入多少次小球才能使所有小球爆炸消失掉。输入样例：3AAABAAA3ABBABBA输出样例：22说明：共有5个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为5、10、15、30和40分，对每个测试数据集分别执行一次程序，每次必须在运行时限30秒内结束程序并输出正确的答案才能得分。所有数据均从标准输入设备（stdin/cin）读入，并写出到标准输出设备 （stdout/cout）中。五个测试数据集中输入初始小球队列的长度分别不大于10、20、50、100和200，各有不超过5000组测试数据。
{:3_59:}{:3_59:}{:3_59:}{:3_59:} {:3_53:}一共有几种颜色的小球呢？ 讲得不错哦，顶楼主
呵呵，不错 谢谢，题目好难 就你这个样子，这个年龄，已经跌破发行价了。
~~~~哼..哼..哼...
我身边的朋友们啊，你们快点出名吧，这样我的回忆录就可以畅销了
赫赫
谢谢哦，辛苦辛苦！
页:
[1]
2