Description

小小秦是小秦的弟弟，他才学会加法。

小秦现在想考试一下弟弟对加法的掌握程度，但他又不想出平时学校老师出的那些题

于是他给出一串数字S，再给出一个整数N。

问弟弟这样一个问题 在S中添加几个加号，可以使得表达式的结果为S。

例如 S="303",N=6 则只最少只要一个加号就可以了即3+03=6

S="1110",N=3 则最少要加3个加号，即1+1+1+0=3

Format

Input

第1行：1个字符串S(1 ≤ S的长度 ≤ 40) 和1个整数N(N≤100000)。

S和N用1个空格分隔。

Output

第1行：1个整数K，表示最少的加法次数让S等于N。

如果怎么做都不能让S等于N，则输出-1。

Samples

【输入样例】

输入数据 1

99999 45

输出数据 1

4

 思路：

这道题采用（深度优先）算法。

我们可以模拟添加加号的位置：

用指向当前数， 

记下当前的累加和（并不一定加到的深度），

再记下当前的加数

和加号的个数（拼音大法）

注意，关于有两种操作：

是会延长的，它可以与当前指向的数合并，但不会累加，不然会很麻烦，因为有记下累加和就够了。如：当前，当前指向数字，则可以与合并为；

加到里更新累加和，此时变成指向的数,此时加号个数也要加一

 我们做就可以按这两种操作来做 

代码：

#include
using namespace std;
const int N= 210;
string s;
int len;
int m;
int ans=INT_MAX;//答案 
int zhuan(char ss) {//转换器，将字符型转成整型 
	if(ss=='0') return 0;
	if(ss=='1') return 1;
	if(ss=='2') return 2;
	if(ss=='3') return 3;
	if(ss=='4') return 4;
	if(ss=='5') return 5;
	if(ss=='6') return 6;
	if(ss=='7') return 7;
	if(ss=='8') return 8;
	if(ss=='9') return 9;
}
void dfs(int dep,int sum,int jia,int now_num) {
	if(sum>m) return ;//如果sum比要求的和m还大，可以return了 
	if(dep==len) {//如果已经遍历完这串数 
		if(sum+now_num==m) //且sum为要求的和m 
		    ans=min(jia,ans);//更新答案 
		return ;//一定要return 
	}
// 01DFS: 
	dfs(dep+1,sum,jia,now_num*10+zhuan(s[dep]));
	//now_num它可以与当前dep指向的数合并
	dfs(dep+1,sum+now_num,jia+1,zhuan(s[dep]));
	//也可以把now_num加到sum中，此时jia+1 
}
int main() {
	cin>>s>>m;
	len=s.size();//获取长度 
	dfs(0,0,0,0); 
	if(ans==INT_MAX) puts("-1");
	else
		cout<

对，你没有看错，了，这说明没完

于是我又加了几个剪枝：

 正解：

#include
using namespace std;
const int N = 210, M = 100010;
string s;
int len;
int m;
int ans = INT_MAX;
int bs[N];

int ss[M]; 
 
int zhuan (char ss)
{
	if (ss == '0') return 0;
	if (ss == '1') return 1;
	if (ss == '2') return 2;
	if (ss == '3') return 3;
	if (ss == '4') return 4;
	if (ss == '5') return 5;
	if (ss == '6') return 6;
	if (ss == '7') return 7;
	if (ss == '8') return 8;
	if (ss == '9') return 9;
}
void dfs (int dep, int sum, int jia, int now_num)
{
	if (sum > m) return ;
	if (now_num + sum > m) return ;
	if (dep == len)
	{
		if (sum + now_num == m) ans = min (jia, ans);
		return ;
	}

	if (sum + bs[len - 1] - bs[dep] > m) return ;
	//如果把dep到末位的数一个个加起来都大于m的话就return吧 
	if (ss[sum])//如果不是最优的，return； 
		if (ss[sum] < jia) return ;
	ss[sum] = jia;//否则更新最优的 
	
	dfs (dep + 1, sum, jia, now_num * 10 + zhuan (s[dep]) );
	dfs (dep + 1, sum + now_num, jia + 1, zhuan (s[dep]) );
}
int main()
{
	cin >> s >> m;
	len = s.size();
	bs[0] = zhuan (s[0]);
	for (int i = 1; i < len; i++)//做前缀和 
		bs[i] = bs[i - 1] + zhuan (s[i]);
	dfs (0, 0, 0, 0);
	if (ans == INT_MAX) puts ("-1");
	else
		cout << ans << endl;
	return 0;
}