【洛谷 P7296】 【状压DP】 Uddered but not Herd G

【洛谷 P7296】 【状压DP】 Uddered but not Herd G

题目

解题思路

qwq数据范围才20，很明显是状压啦
如果s[i]>=s[j]说明又多读一次了 s表示的是它在字母表中出现的位置
先将字母离散化
然后求出c[j][k] 指的是第k种字符出现在第j种字符后面的个数，k比j在字母表出现的更早，代表了要多读的次数
枚举字母表当前的状态s
枚举当前添加的字符j
转移式为

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
string s;
int len,tot,pos[100010],v[100010],z[100010],h[30],c[30][30],f[1<<21];
int main()
{cin>>s;len=s.size();memset(f,0x7f,sizeof(f));f[0]=1;for (int i=1;i<=len;i++){pos[i]=s[i-1]-96;v[s[i-1]-96]++;}for (int i=1;i<=26;i++)if (v[i]) h[i]=++tot;for (int i=1;i<=len;i++)z[i]=h[pos[i]];  //离散化for (int i=1;i<len;i++) c[z[i]][z[i+1]]++;for (int i=1;i<=(1<<tot)-1;i++)  //枚举字母表for (int j=1;j<=tot;j++)  //枚举新添的字符if (i&(1<<(j-1))){int sum=f[i^(1<<(j-1))];for (int k=1;k<=tot;k++)   //枚举字母表里的比j早出现却在它后面的字符，求要多读的次数if (i&(1<<(k-1))) sum+=c[j][k];f[i]=min(f[i],sum);}printf("%d",f[(1<<tot)-1]);return 0;
}