题目描述
有N个人，来自K个家族.他们排成一行准备照相，但是由于天生的排外性，每个人都希望和本家族的人站在一起,中间不要加入别的家族的人.问最少从队列中去掉多少个就可以达到这个目的.
输入格式
第一行给出N,K。N在[1,100]，K在[1,5]
第二行给出N个数，每个数为1到K中的某个数。
输出格式
最少从队列中去掉多少个就可以达到这个目的
显然对于当前第i个点我们可以做两个操作：留下或者删去。
如果留下，就会有两种情况：第i个人和上一个留下的人属于同一个家族。第二种情况是不属于同一个家族，那么我们的状态需要从当前有人留下的家族转移过来。
如果删去则不需要考虑任何东西。
综合上面的分析，可以知道我们需要的信息有：当前是第几个人，当前选了那些家族，处理完当前人之后最后一个留下的人的家族。
那么可以设计出这样的状态：dp(i,j,k)，表示当前为第i个人，当前选的家族情况的二进制表示为j，最后一个留下的人的家族为k。设第i个人的家族为col，那么可以得出状态转移方程：
[dp[i][j][col]=Max_{1≤k≤K}{{}dp[i-1][j{wedge}R(1<<col)][k]+1{}}
]
初始化都为0，答案为n-Max{dp(n,i,j)}
时间复杂度为O(NK * 2^K)。
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 101
#define maxm 6
using namespace std;
int dp[maxn][1<<maxm][maxm];
int n,m,ans;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(x=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int main(){
//freopen("photo.in","r",stdin);
//freopen("photo.out","w",stdout);
n=read(),m=read();
for(register int i=1;i<=n;i++){
int col=read()-1;
memcpy(dp[i],dp[i-1],sizeof dp[i-1]);
for(register int j=0;j<1<<m;j++) if(j&(1<<col)){
dp[i][j][col]=max(dp[i][j][col],dp[i-1][j][col]+1);
for(register int k=0;k<m;k++){
dp[i][j][col]=max(dp[i][j][col],dp[i-1][j^(1<<col)][k]+1);
}
}
}
for(register int i=0;i<1<<m;i++){
for(register int j=0;j<m;j++){
ans=max(ans,dp[n][i][j]);
}
}
printf("%d
",n-ans);
return 0;
}