这种和操作顺序有关的,没啥性质的,可以思考如果操作的集合相同,他的状态是不是相同,如果是的话,可以考虑(2^n)状压记忆化而非直接(n!)枚举顺序。
那么显然这题满足这个性质。
我们直接(2^p n)做就行了。
这个程序有点卡常。
#include<iostream>
#include<cstdio>
#define ll long long
#define N 20
int n,p;
int a[N][N];
std::string S;
int ans = 1e6;
inline bool check(std::string s,int to){
int lim = s.size();
int las = -1;
for(int i = 0;i < lim - 1;++i){
if((s[i] == 'a' + to && s[i + 1] != 'a' + to) && (!a[s[las] - 'a'][s[i + 1] - 'a'] && las != -1))
return 0;
if(s[i] != 'a' + to)
las = i;
}
return 1;
}
inline int slove(int now,std::string s){
// std::cout<<now<<" "<<s<<":"<<std::endl;
int k = s.size();
ans = std::min(k,ans);
for(int i = 0;i < p;++i){
if(!(now >> i & 1)){
if(check(s,i)){
std::string to;
to.clear();
int lim = s.size();
for(int j = 0;j < lim;++j)
if(s[j] != 'a' + i)
to.push_back(s[j]);
// std::cout<<i<<" "<<to<<std::endl;
slove(now | (1 << i),to);
break;
}
}
}
}
int main(){
scanf("%d%d",&n,&p);
std::cin>>S;
for(int i = 0;i < p;++i)
for(int j = 0;j < p;++j){
scanf("%d",&a[i][j]);
}
slove(0,S);
std::cout<<ans<<std::endl;
}
值得注意的是,我们并不在乎插入的顺序,我们只在乎这个集合,所以我们找到第一个后就退出。