【Luogu_P7296】【USACO21JAN】 Uddered but not Herd G

思路：

状压DP，把字符缩成01串，如果需要重唱就贡献加1

$code$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>using namespace std;char s[100100];
int a[101010], b[101010], c[200][200];
int n, f[1<<21];int main()
{scanf("%s", s+1);n=strlen(s+1);;for(int i=1; i<=n; i++)b[i]=s[i];sort(b+1, b+1+n);int tot=unique(b+1, b+1+n)-b-1;for(int i=1; i<=n; i++)	a[i]=lower_bound(b+1, b+1+tot, s[i])-b-1;for(int i=1; i<n; i++)c[a[i]][a[i+1]]++;memset(f, 0x3f, sizeof(f)), f[0]=1;for(int i=1; i<(1<<tot); i++)for(int j=0; j<tot; j++)if(i&(1<<j)){int s=f[i^(1<<j)];for(int k=0; k<tot; k++)if(i&(1<<k))s+=c[j][k];f[i]=min(s, f[i]);}printf("%d", f[(1<<tot)-1]);return 0;
}