题目链接：http://acm.swust.edu.cn/problem/0581/
Time limit(ms): 1000 Memory limit(kb): 65535
Description
把m个含有k种不同颜色的石子放成一条线上。现在要问你怎么才能取走
最少的石子，使得没有两个相同颜色的石子之间含有其它的颜色
最少的石子，使得没有两个相同颜色的石子之间含有其它的颜色
Input
有多组测试数据，每组测试数据有两行，第一行是m和k，1<=m<=100，
1<=k<=5，第二行就是那m个石子的颜色，用1到k表示，最后输入0 0表示
程序结束。
1<=k<=5，第二行就是那m个石子的颜色，用1到k表示，最后输入0 0表示
程序结束。
Output
对于每组测试数据，请你找出最少取走的石子数目并输出
Sample Input
|
10 3
2 1 2 2 1 1 3 1 3 3
0 0
|
Sample Output
| 2 |
解题思路：状态压缩dp,一共最多5类石子,那么
(1)dp[1<<5][5]用来表示(二进制每一位对应)是否含有第k类石子，表示以第k类石子结尾含有1<<5(二进制数)每一位对应种类石子下的可行序列最大值
(2)题目中给出的种类是从1开始的这里我们要转化为从0开始否则1<<6浪费空间(算一个小小的优化吧~~~)
(3)在0-1<<5中查找不同的状态i&(1 << x) 表明前面含有x类石,那么可以直接dp[i][x]++
(4)在(3)执行完以后，如果!(i&(1 << x)) 加一生成的新段如果此时dp值大于相同状态的值，更新即
for (L = ; L < k; L++){
if (L != x && dp[j | ( << x)][x] < dp[j][L] + ) //不含x类的段加一生成的新段如果大于相同状态的值，更新
dp[j | ( << x)][x] = dp[j][L] + ;
}
(5)最后查询所有dp[1<<k-1][i]状态下的最长可行序列，用总长度减去即可
dp方程总结如下
每输入一个x
if(s&(1<<x)
dp[s][x] = dp[s][x] + 1
else
dp[1<<x|s][x] = max(dp[1<<x|s][x],dp[s][L]+1) L(0,k)
代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int m, k, dp[ << ][];
//dp[][k] 二进制每一位对应含有第k类石子，表示以第k类石子结尾含有1<<5每一位对应下石子的最大值
while (cin >> m >> k, m || k){
int i, x, j, L, t = << k, maxn = ;
memset(dp, , sizeof(dp));
for (i = ; i < m; i++){
cin >> x;
x--;
for (j = ; j < t; j++){
if (j&( << x)) //对于前面也是以x类石子结尾的最大值直接加1
dp[j][x]++;
}
for (j = ; j < t; j++){
if (!(j&( << x))) //前面不含x类石子
for (L = ; L < k; L++){
if (L != x && dp[j | ( << x)][x] < dp[j][L] + ) //不含x类的段加一生成的新段如果大于相同状态的值，更新
dp[j | ( << x)][x] = dp[j][L] + ;
}
}
}
for (i = ; i<k; i++)
if (dp[( << k) - ][i]>maxn)
maxn = dp[( << k) - ][i];
cout << m - maxn << endl;
}
return ;
}