有一行彩色的棋子，每个棋子的颜色是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

我不是伸手党，我自己思考了很长时间不知道如何下手，好吧，新手伤不起

#include <iostream>

using std::cin;
using std::endl;
using std::cout;

void main()
{
    int n=1,a[100],b[100],x(0),xx(0);
    int y;
    while(cin>>y)
    {
        
        b[xx]=y;
        xx++;
        if(y>5)
        {
        }
        else
        {
           a[x]=y;
           x++;
        }
    }
    cout<<"输入的棋子的顺序为："<<endl;
    for(int w=0;w<xx;w++)
        cout<<b[w]<<" ";
    int s(0);
    for(int i=0;i<x;)
    {
        int j=i+1,z=i+2;
        if(a[i] == a[z])           //判断是否为同色
        {
            if(a[j] != a[i])       //判断中间棋子的颜色
            {
                s++;                //如果中间棋子颜色与旁边不同，移走
                i+=2;              //a[j]被移走了，下一个应该是a[z]
            }
        }
        else
            i++;
    }

    cout<<endl<<"需至少移走的棋子的数量为："<<s<<endl;
}


只测试了你给出的样例

互学！

考虑了一小时二十分钟，目前只想到空间压缩后提取所有可行解的方法，但如何描述最优解映射的方法暂时想不出来，呵呵

加上过程记录的话肯定能实现，但应该有更好的方法吧……

。。。

[ 本帖最后由 ying8501 于 2014-5-19 09:36 编辑 ]

BFS可解，也许有更快的。

再等等吧。

http://blog.

楼主可以参考一下。