题解：【USACO 21JAN】P7296 Uddered but not Herd G
JXR_Kalcium
·
·
题解
题目大意
给出一个字符串 s，要找一个字串，按照这个字串给 s 分段，求最少段数。
例：当 s=\textrm{mildredree}，字串为 mildre 时，就可以划分为 3 个部分，为 mildre/dre/e。
解题思路
暴力
题目中给出 s 中的字母要么只有 mildre，要么只有除了 mildre 之外的所有字母，所以 s 中最多只有 20 个字母。于是我们可以通过深搜枚举这些字母所有的排列方式，再通过一次 O(N) 的循环扫一遍，统计部分即可，时间复杂度 O(N)，常数 20!。
状压 DP
很明显，就拿样例来说，字串中有一个 de，假如在 s 中找到了 ed，那么肯定要再分一个段；同样对于 md、ld 等也是如此。于是我们就可以发现其实不用关心子串是什么，只要知道哪些字母出现过，以及哪些字母的位置相反即可。所以此题满足无后效性，最多又只有 20 个字母，可以用状压 DP 来做。
先对 s 中所有出现的字母离散化，按照字母表（0\sim25）顺序分别标号 0\sim cnt-1（出现的字母个数为 cnt），记录在 t_i 中，然后统计 s 中每两个相邻字母出现的个数 c_{i,j}。例如对于样例中的 s，就有离散化后的 t_3=d=0, t_4=e=1, t_8=i=2\cdots，这个时候 c_{12,8}=1（m 和 i 相邻）。
然后这 cnt 种字母中每个都有选或不选（1/0）两种状态，于是就可以枚举 1\sim 2^{cnt}-1 这些状态。设 f_i 表示状态为 i 时最少的分段数，那么我们可以枚举这一个状态中已经选了的字母 j，于是上一个转移过来的状态就应该是 i-2^j（f_0=1，因为一个都不选就只有一个段）。
接下来再去看，如果我们把 j 加进来后会多出多少个段。可以再枚举一下已经选了的字母 k，那么多出来的段数自然就是 c_{j,k}。综上所述，动态转移方程为：
最后的答案即是 $f_{2^{cnt}-1}+1$，时间复杂度 $O(2^{cnt}\times cnt^2)$，最多只有 $419430400$ 次循环，开吸氧能过。
## AC 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,bz[31],t[31],c[31][31],cnt,f[2000001]={1},sum;
char s[100001];
int main()
{
scanf("%s",s); n=strlen(s);
for(int i=0; i<n; ++i) bz[s[i]-97]=1;
for(int i=0; i<26; ++i) t[i]=bz[i]?cnt++:0;
for(int i=1; i<n; ++i) ++c[t[s[i-1]-97]][t[s[i]-97]];
for(int i=1; i<(1<<cnt); ++i) f[i]=INT_MAX;
for(int i=1; i<(1<<cnt); ++i)
{
for(int j=0; j<cnt; ++j)
{
if(!(i&(1<<j))) continue; sum=0;
for(int k=0; k<cnt; ++k)
{
if(i&(1<<k)) sum+=c[j][k];
}
f[i]=min(f[i],f[i-(1<<j)]+sum);
}
}
printf("%d",f[(1<<cnt)-1]+1);
return 0;
}
```