题目：传送门
题意
思路
看数据很容易想到二维 DP，只不过只想到 DP 还远远不够。
和不超过 20 的字符串不超过 2500 个，长度最长为 20。
那我们可以先暴力预处理出这些字符串，并建 trie 树.
用 dp[i][j] 表示处理完前 i 个字符，后缀在 trie 树上对应着 节点 j 的满足题目条件的答案.
能想到这里，题目也就解决了
#include <bits/stdc++.h> #define LL long long #define ULL unsigned long long #define UI unsigned int #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF 0x3f3f3f3f #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second #define lb(x) ((x) & (-(x))) #define dbg(x) cout<<#x<<" = "<<x<<endl; using namespace std; const int N = 1e6 + 5; int x; char a[N]; vector < int > tmp; int dp[2][N]; int t[N][10]; int vis[N]; int fail[N]; int cnt = 0; void add() { int rt = 0; for(auto v : tmp) { if(!t[rt][v]) t[rt][v] = ++cnt; rt = t[rt][v]; } vis[rt] = 1; } void getfail() { queue < int > Q; rep(i, 0, 9) { if(t[0][i]) { fail[t[0][i]] = 0; Q.push(t[0][i]); } } while(!Q.empty()) { int now = Q.front(); Q.pop(); rep(i, 0, 9) { if(t[now][i]) { fail[t[now][i]] = t[fail[now]][i]; Q.push(t[now][i]); } else t[now][i] = t[fail[now]][i]; } } } bool judge() { for(int i = 0; i < tmp.size(); i++) { int s = 0; for(int j = i; j < tmp.size(); j++) { s += tmp[j]; if(x % s == 0 && s < x) return false; } } return 1; } void dfs(int now) { if(now == x) { if(judge()) add(); return ; } rep(i, 1, 9) { if(now + i <= x) { tmp.pb(i); dfs(now + i); tmp.pop_back(); } } } void solve() { scanf("%s %d", a, &x); dfs(0); getfail(); int n = strlen(a); rep(i, 0, cnt) dp[0][i] = dp[1][i] = INF; dp[0][0] = 0; int fir, sec; rep(i, 0, n - 1) { fir = i & 1, sec = fir ^ 1; rep(j, 0, cnt) { dp[sec][j] = INF; } rep(j, 0, cnt) { dp[sec][j] = min(dp[sec][j], dp[fir][j] + 1); /// 删掉第 i 个字符 int rt = t[j][a[i] - '0']; if(!vis[rt]) dp[sec][rt] = min(dp[sec][rt], dp[fir][j]); } } int ans = INF; rep(i, 0, cnt) ans = min(ans, dp[sec][i]); printf("%d ", ans); } int main() { // int _; scanf("%d", &_); // while(_--) solve(); solve(); return 0; }