【NOIP模拟赛】狐狸的谜语

2014年10月28日1,8390

题目描述

话说某一个月黑风高的晚上,一只褐色的狐狸快速地跳过了一只懒狗,并留下一个字符串“032089”和一个数字5。

这其中一定隐含了某些秘密!酷爱思考的你马上发现,这个字符串可以写成:“03+2+0*89”,结果为5。这是一个非常有趣的问题!

现在给出一个长度为N的数字字符串和一个数字T,要求插入最少的加号或者乘号,使得数字字符串的运算结果为T。运算符*号优先级高于+号,运算数可以有任意个前导0。

榆入格式

输入不超过5组数据,每组数据两行。

每组数据的第1行为长度为N,只包含0~9的数字字符串,第2行为一个数字T。

输入T<0表示输入结束。

输出格式

输出一个数字单独占一行,表示最少需要添加的运算符(+号或*号)数,无解输出-1。

输入样例

032089

5

333

9

00

-1

输出样例

3

2

数据范围

对于30%的数据,有1≤N≤10,0≤T≤50。

对于50%的数据,有1≤N≤15,0≤T≤200。

对于全部的数据,有1≤N≤20,0≤T≤200。

这题dp做法好像很麻烦

这么小的范围还是搜索大法好

3^20搜索

预处理出v[i][j]->i-j的连续数字构成的数

然后搜索过程记录当前搜索的深度,所用符号数,前一个符号的位置,最后几个乘数的乘积,式子当前的结果

为了避免过程中爆int,把>v[i][j]的赋值为t+1

剪枝就是若当前最后几个乘数的乘积加上式子当前结果大于t,且这个位置之后的数字没有0,直接retrun

还可以迭代深搜或者二分