题目描述：
给你一个字串，你每次可以选择一段连续的相同的字符删去，但是你以但选择了一种类型，你就必须把这个类型的所有区间段都删去，才可以考虑选下一种类型。问最少几步可以清空字串。
题目分析：
对于字符串中的种类其实是特别少的 那么我们可以枚举状态 1表示在这个状态里这种字符已经全部消去了
对于状态i来说 我们可以枚举其中消去的字符j 然后从i状态去除j的状态转移过来 现在的问题就是对于去除了j的状态需要花几次去消出所有的j。
我们可以预处理一个cnt[sta][i]数组表示的是在sta这个状态下去除所有的i字符需要多少次
时间复杂度是O(2k?k)O(2^k*k)O(2k?k)
题目链接：
Vjudge
代码：
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
std::map<char,int> used;
const int maxm=401;
const int inf=0x7ffffff;
int dp[(1<<20)+10];
int cnt[(1<<20)+10][30],val[maxm],stk[maxm];
char s[maxm];
int n,m,tot;
inline void init(int sta)
{
int top=0;for(int i=1;i<=n;i++)if(!((1<<val[i])&sta)) stk[++top]=val[i];for(int i=1;i<=top;i++)if(i==1||stk[i]!=stk[i-1]) cnt[sta][stk[i]]++;/*for(int i=0;i<m;i++) printf("%d ",cnt[sta][i]);puts("");*/
}
int main()
{
scanf("%d%d",&n,&m);scanf("%s",s);for(int i=1;i<=n;i++){
if(used.find(s[i-1])==used.end()) used[s[i-1]]=++tot;val[i]=used[s[i-1]]-1;//printf("%d ",val[i]);}//puts("");for(int i=0;i<=(1<<m)-1;i++) init(i);for(int i=1;i<=(1<<m)-1;i++){
dp[i]=inf;for(int j=0;j<m;j++)if((1<<j)&i) dp[i]=std::min(dp[i],dp[i^(1<<j)]+cnt[i^(1<<j)][j]);//printf("%d %d\n",i,dp[i]);}printf("%d\n",dp[(1<<m)-1]);return 0;
}