F. x-prime Substrings （自动机上dp+滚动数组压维）

做法

dfs跑出 所有题意上的串 并插入字典
那么我们就是找一个最长的不包含这些串的 最小操作数
dp[i][j] 表示的 前i个序列的最小操作数
如果 下一个状态没有被标记 f[i+1][p]=min(f[i+1][p],f[i][j])
另一种情况是删除 i+1 那么 f[i+1][j]=min(f[i+1][j],f[i][j]+1)
滚动数组优化一下即可

#include 
using namespace std;
const int N = 4e4 + 5;
const int M = 1e4 +10;
int n, x, cnt, son[M][10], f[N], ed[N], g[N][2];
string s;
void insert(string s) {
	int p = 0;
	for(auto c : s) {
		if(!son[p][c - '0'])son[p][c - '0'] = ++cnt;
		p = son[p][c - '0'];
	}
	ed[p] = 1;
}
void build() {
	queue <int> q;
	for(int i = 0; i < 10; i++)if(son[0][i])q.push(son[0][i]);
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		for(int i = 0; i < 10; i++)
			if(son[t][i])q.push(son[t][i]), f[son[t][i]] = son[f[t]][i];
			else son[t][i] = son[f[t]][i];
		ed[t] |= ed[f[t]];
	}
}
bool check(string s) {
	for(int i = 0; i < s.size(); i++)
		for(int j = i; j < s.size(); j++) {
			int cnt = 0;
			for(int k = i; k <= j; k++)cnt += s[k] - '0';
			if(cnt < x && x % cnt == 0)return 0;
		}
	return 1;
}
void dfs(int num, string s ) {
	if(num == x) {
		if(check(s))insert(s);
		return;
	}
	for(int i = 1; i < 10; i++)
		if(num + i <= x)
			dfs(num + i, s + (char)(i + '0'));
}

int main() {
	cin >> s >> x, dfs(0,""), build();
	s = " " + s;
	for(int i = 1; i < N; i++) {
		for(int j = 0; j < 2; j++) {
			g[i][j] = 1 << 30;
		}
	}
	g[1][1] = 0;
	for(int i = 1; i <= s.size() - 1; i++) {
		for(int j = 0; j <= cnt; j++) g[j][0] = g[j][1], g[j][1] = 1 << 30;
		for(int j = 0; j <= cnt; j++) {
			g[j][1] = min(g[j][1], g[j][0] + 1);
			int p = son[j][s[i] - '0'];
			if(!ed[p])g[p][1] = min(g[p][1], g[j][0]);
		}
	}
	int ans = 2e9;
	for(int i = 0; i <= cnt; i++)ans = min(ans, g[i][1]);
	cout << ans << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67