【8.17模拟赛T2】【洛谷P7296】Uddered but not Herd G【状压DP】

题目链接：https://www.luogu.com.cn/problem/P7296

分析

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;int n;
int f[1<<20],a[100001],b[100001],c[1001][1001];
char s[100001];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-1;i++){c[a[i]][a[i+1]]++;}memset(f,0x3f,sizeof(f));f[0]=1;for(int ss=1;ss<=(1<<m)-1;ss++){for(int j=0;j<=m-1;j++){if(ss&(1<<j)) {int sum=f[ss^(1<<j)];for(int k=0;k<=m-1;k++){if(ss&(1<<k)) sum+=c[j][k];}f[ss]=min(f[ss],sum);}}}cout<<f[(1<<m)-1];return 0;
}
//mildredree