前言(废话):这是作者最后一发题解了(9月30日以前)...

思路：

使用f[i][j]数组记录以第i个数作为结尾，总和为s的最小加号数，num[i][j]表示数字字符从i加到j的数值(区间和)。

初始化num数组：

//lens表示字符串的长度
  for(int i=1;i<=lens;i++){
		for(int j=i;j<=lens;j++){
      //前缀和转区间和，因为string下标从0开始，所以为s[j-1]-'0'
			num[i][j]=num[i][j-1]*10+(s[j-1]-'0');
		}
	}

动态规划部分：

第一层枚举遍历每一位数字(i=1->lens) ，第二层遍历总和和，从0到目标n(k=0->n),第三层从后往前枚举i之前的加号数(k=i-1->0)

第三层为什么是从i-1到0而不是0-到i-1呢？因为首先由于是第 j 位，所以f的第一维填j；其次，由于k加上了加号，所以应该找它的上一个状态，也就是以j结尾，以k减去从j+1到i的(num[j + 1][i])为和的加号数(也就是 dp[j][k - num[j + 1][i]]),所以为了更新上一个状态，需要从i-1到0。

for(int i=1;i<=lens;i++){
		//遍历和，从0到目标n
		for(int k=0;k<=n;k++){
			//从后往前枚举i之前的加号数
			for(int j=i-1;j>=0&&num[j+1][i]<=n;j--){
				//如果从j+1到i的数大于所枚举的k,就不处理
				if(k>=num[j+1][i]){
					//如果可以增加一个加号，就比较大小 
					f[i][k]=min(f[i][k],f[j][k-num[j+1][i]]+1);
				}
			}
		}
	}

如何判断-1(题干:如果怎么做都不能让s于n,则输出−1)

输出为f[lens][n],为加号总数，判断是否大于40，因为题目保证1≤len(s)≤40，所以加号总数绝对不大于len(s)。

  if(f[lens][n]<40)cout<<f[lens][n];
	else cout<<-1;

易错事项：

1.num数组和f数组要开long long,不然容易爆

2.f数组要初始化最大值(作者是1e5+5),因为要求最小值

题解部分来源于此处，不明白可以自己看看

https://www.luogu.com.cn/problem/solution/P1874

后言:付伙承宫

还没写完

先放代码再解释

#include<bits/stdc++.h>
using namespace std;
int dp[41][100001];
int num[41][100001];int len=0,n;
string s;
int main(){
	cin>>s>>n;
    len=s.size();
    memset(dp,0x3f3f3f3f,sizeof dp);
    for(int i=1;i<=len;i++)num[i][i]=s[i-1]-'0';
    for(int i=1;i<=len;i++){
        for(int j=i+1;j<=len;j++){
        	if(0LL+num[i][j-1]*10+s[j-1]-'0'>100000)num[i][j]=100010;
            else num[i][j]=num[i][j-1]*10+s[j-1]-'0';
        }
    }
    dp[0][0]=-1;
	for(int i=1;i<=len;i++){
        for(int k=0;k<=n;k++){
            for(int j=i-1;j>=0;j--){
                if(k>=num[j+1][i]&&num[j+1][i]<=100000){
                    dp[i][k]=min(dp[i][k],dp[j][k-num[j+1][i]]+1);
                }
            }
        }
    }
	if(dp[len][n]<40&&dp[len][n]>=0)cout<<dp[len][n];
	else cout<<"-1";
	return 0;
}

解释：

1、num数组

num[i][j]表示第i个到第j个表示的数

例如：