[USACO21JAN] Uddered but not Herd G

首先考虑一个问题，如果字母表已经确定，如何将原串分割是最优的。

设原串为 $s$ ，原串中字母共有 $n$ 种，我们认为各个字符之间是可以比较的，在确定的字母表中，靠前的字母比靠后的字母小。

对于原串 $s$ ，若有 $s_i \geq s_{i+1}$ 显然 $s_i$ 和 $s_{i+1}$ 是要被“分割”开的

也就是说，对于这个确定的字母表，$s_i$ 和 $s_{i+1}$ 不会在同一个周期被念出来，$s_i$ 对答案的贡献为 $1$ 。

观察数据范围，发现 $n \leq 20$ ，这个数据范围是可以状压的，设集合 $S$ 表示当前加入的字母的集合，$f_S$ 表示 $S$ 集合中的字母对答案的贡献的最小值为多少。

维护向集合 $S$ 中加入字母 $c_j$ 的过程，根据我们上面得出的结论，$c_j$ 的贡献就是集合 $S$ 中满足字符位置为 $c_j$ 在原串中的下一位且小于等于 $c_j$ 的字符个数（相同的字符可能有多个位置满足要求），这个是可以预处理出来的。

于是根据上面的过程，我们可以得到状态转移方程：

$$f_S=\min_{c_j \in S}\{f_{S\backslash \{c_j\}}+\sum_{c_k \in S} cost_{j,k}\}$$

令初始状态为 $f_{\varnothing}=1$，因为要将第一次念字母表计算进去，最终答案为 $f_{S=\{c_1,c_2, \dots, c_n\}}$。

其中 $cost_{j,k}$ 表示在原串中所有 $c_j$ 的位置中满足 $c_k \leq c_j$ 且 $c_k$ 为 $c_j$ 的下一位的个数，将原串 $c$ 离散化之后可以预处理出来。

时间复杂度: $\mathcal{O(2^n\ast n^2)}$ 。

既然你能找到这题，我相信你能瞬间做出来的。

Code:

#include<bits/stdc++.h>
typedef long long LL;
typedef long double LD;
using namespace std;
const int N=21,M=100010,INF=0x3f3f3f3f;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
int n,m,ans=INF,f[1<<20],a[M],b[M],c[N][N];
char s[M];
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+n+1);
	int m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+m+1,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 S=1;S<(1<<m);S++)
		for(int j=0;j<m;j++)
			if(S&1<<j){
				int sum=f[S^1<<j];
				for(int k=0;k<m;k++)
					if(S&1<<k)sum+=c[j][k];
				f[S]=Min(f[S],sum);
			}
	printf("%d\n",f[(1<<m)-1]);
	return 0;
}