This way
给你一个串，然后给你每两种字符之间的关系，1表示可以相邻，否则是0,。你每次可以消去一种字符，剩下的字符按照原来的顺序拼接起来，并且满足字符之间的关系，问你最后这个串的长度最短是多少。
如果当前有这么一个串：acbeda 假设ab是不能相邻的，那么假设0表示未消去，1表示消去， 那么00100,00011这两个是不合法的，并且所有包含它们的状态都是不合法的，我们将所有不能相邻的情况都做一遍。通过SOSDP就可以得到所有不可行的状态。然后枚举当前状态，如果这个状态合法，我们看看能不能找到一条路通向这个状态，如果没有，那么这个状态依旧不合法。
#include<bits/stdc++.h> using namespace std; const int N=1<<17,M=1e5; char s[M]; bool dp[N],no[N],mp[17][17],vis[N]; int num[N],n,k; void dfs(int s) { if(vis[s])return ; vis[s]=1; for(int i=0;i<k;i++) { if(s&(1<<i)) { dfs(s^(1<<i)); dp[s]|=dp[s^(1<<i)]; } } } void solve(char a,char b) { memset(dp,0,sizeof(dp)); int l=-1; for(int i=0;i<n;i++) { if(s[i]==a||s[i]==b) { l=i; break; } } if(l==-1)return ; int ss=0,r=l+1; while(l<=n) { while(r<=n) { if(s[r]==a+b-s[l]) break; else if(s[r]==s[l]) { l=r,r++,ss=0; continue; } ss|=(1<<(s[r++]-'a')); } if(r>n)break; dp[ss]=1; l=r,r++; ss=0; } int sta=(1<<k)-1; sta^=(1<<(a-'a')); if(a!=b) sta^=(1<<(b-'a')); memset(vis,0,sizeof(vis)); dfs(sta); for(int i=1;i<(1<<k);i++)no[i]|=dp[i]; } int main() { scanf("%d%d%s",&n,&k,s); int mx=1<<k; for(int i=0;i<n;i++) num[1<<(s[i]-'a')]++; for(int i=0;i<k;i++) for(int j=0;j<mx;j++) if(j&(1<<i)) num[j]+=num[j^(1<<i)]; for(int i=0;i<k;i++) { for(int j=0;j<k;j++) { scanf("%d",&mp[i][j]); if(!mp[i][j]) solve(i+'a',j+'a'); } } int ans=0; for(int i=1;i<mx;i++) { if(no[i])continue; no[i]=1; for(int j=0;j<k;j++) { if(i&(1<<j)&&!no[i^(1<<j)]) { no[i]=0; ans=max(ans,num[i]); break; } } } printf("%d\n",n-ans); return 0; }