upd on 2023/12/22：修改了代码，现已通过所有 hack 数据。
首先定义状态：
-
令 \(dp_{i,j}\) 表示前 \(i\) 个数字要变成 \(j\) 所需要的最少加号个数。
-
同时，我们还需要一个辅助数组：令 \(num_{i,j}\) 表示 \(i \sim j\) 的数字组成的数（不添加加号）。
然后进行转移。
显然可以枚举每个添加加号的位置 \(i\)，再枚举当前位置与上一个添加加号的位置的距离 \(k\)，然后枚举前 \(i\) 个数要变成的数 \(j\)，于是易得转移方程：
\[dp_{i,j}=\min(dp_{i,j},dp_{i-k,j-num_{i-k+1,i}}+1) \]朴素转移即可。
注意特判 \(dp_{len,n}>len\)（\(len\) 表示字符串 \(s\) 的长度）的情况。
时间复杂度 \(O(n \times len)\)。
需要注意字符串中的 \(0\) 需要剔除，在全 \(0\) 的情形下会影响答案。
代码：
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
string str;
int s,n,tot;
int a[100031];
int num[55][55];
int dp[55][100031];
bool z;
signed main(){
srand(time(0));
cin>>str>>s;
n=str.size();
for(int i=0;str[i];i++){
if(str[i]!='0') z=1;
if(z) a[++tot]=str[i]-'0';
}
for(int i=1;i<=tot;i++){
num[i][i]=a[i];
for(int j=i;j-i<=11&&j<=tot;j++)
num[i][j]=num[i][j-1]*10+a[j];
}
for(int i=0;i<=tot+1;i++)
for(int j=0;j<=s+1;j++)
dp[i][j]=0x7fffffff;
dp[0][0]=0;
for(int i=1;i<=tot;i++)
for(int k=1;k<=11;k++)
if(i>=k)
for(int j=num[i-k+1][i];j<=s;j++)
dp[i][j]=min(dp[i][j],dp[i-k][j-num[i-k+1][i]]+1);
if(dp[tot][s]>tot) cout<<-1;
else cout<<dp[tot][s]-1;
return 0;
}