题意：
给定一个由('1')到('9')组成的字符串(s)和一个数(x)，定义一个串为(x-prime)串，当且仅当这个串上的数字和为(x)，且任意一个不等于本身的子串的和都不是(x)的因子，问最少删多少个数字可以使得串(s)的任何子串都不是(x-prime)串
(1 le |s| le 1000,1 le x le 20)
题解：
由于(x)很小，所以我们可以枚举所有(x-prime)串，然后把所有的(x-prime)串放到(Trie)里面去，因为我们需要原串中没有(x-prime)串，考虑把所有(x-prime)串建AC自动机，然后我们跑一遍(dp)，(dp[i][j])表示(s)串中的第(i)位匹配了自动机上的状态(j)的情况下的最小删除数量
枚举自动机所有的状态(j)，那么存在两种转移：
- 删除下一个点，(dp[i][j] = min(dp[i][j],dp[i-1][j]+1))
- 走到自动机的下一个点，(dp[i][trans[j]] = min(dp[i][trans[j],dp[i-1][j]))
其中第二种转移必须要求AC自动机的下一个点没有匹配到任何的(x-prime)串
由于每个状态只与上一层有关，可以把(dp)数组变为滚动数组
那么，这道题就完成了
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define scs(x) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 1111;
struct AC_automaton{
int ch[MAXN<<5][9],fail[MAXN<<5],tot;
bool tag[MAXN<<5];
void insert(string s){
int p = 0;
for(int i = 0; i < (int)s.size(); i++){
int c = s[i] - '1';
if(!ch[p][c]) ch[p][c] = ++tot;
p = ch[p][c];
}
tag[p] = true;
}
void build_fail(){
queue<int> que;
for(int i = 0; i < 9; i++) if(ch[0][i]) que.push(ch[0][i]);
while(!que.empty()){
int u = que.front();
que.pop();
for(int i = 0; i < 9; i++){
if(!ch[u][i]) { ch[u][i] = ch[fail[u]][i]; continue; }
que.push(ch[u][i]);
int v = ch[u][i];
int pre = fail[u];
while(pre and !ch[pre][i]) pre = fail[pre];
fail[v] = ch[pre][i];
tag[v] |= tag[fail[v]];
}
}
}
int DP(string &s){
vector<int> f(tot+1,INF);
f[0] = 0;
for(char &c : s){
int x = c - '1';
vector<int> next_f(tot+1,INF);
for(int i = 0; i <= tot; i++){
if(f[i]==INF) continue;
cmin(next_f[i],f[i]+1);
if(!tag[ch[i][x]]) cmin(next_f[ch[i][x]],f[i]);
}
f.swap(next_f);
}
return *min_element(all(f));
}
}aho;
bool check(string &dig, int x){
vector<int> pre(dig.size());
pre[0] = dig[0] - '0';
for(int i = 1; i < (int)dig.size(); i++) pre[i] = pre[i-1] + dig[i] - '0';
for(int i = 0; i < (int)dig.size(); i++){
for(int j = i; j < (int)dig.size(); j++){
int S = pre[j] - (i==0?0:pre[i-1]);
if(S!=x and x%S==0) return false;
}
}
return true;
}
void search_dig_string(string &dig, int sum, int x){
if(sum==x){
if(check(dig,x)) aho.insert(dig);
return;
}
for(int i = 1; i < 10; i++){
if(sum+i>x) return;
dig.push_back(i+'0');
search_dig_string(dig,sum+i,x);
dig.pop_back();
}
}
void solve(){
string str;
int x;
cin >> str >> x;
string dig("");
search_dig_string(dig,0,x);
aho.build_fail();
cout << aho.DP(str) << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}