题目描述
话说某一个月黑风高的晚上,一只褐色的狐狸快速地跳过了一只懒狗,并留下一个字符串“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。
题解
dfs，要加一些精妙的剪枝。hzwer ORZ
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,num[25][25],tag,zr[25];
char ch[25];
void pre()
{
int i,j;
memset(num,0,sizeof(num));
memset(zr,0,sizeof(zr));
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{num[i][j]=num[i][j-1]*10+(ch[j]-'0');
if(num[i][j]>m) num[i][j]=m+1;
}
for(i=n;i>0;i--)
{if(ch[i]!='0') zr[i]=1;
else break;
}
}
void dfs(int w,int sum,int last,int mul,int ct,int tot)
{
if(sum>m||tag||ct>tot) return;
if(w==n)
{if(sum+mul*num[last+1][n]==m) tag=1;
return ;
}
if(zr[w-1]&&sum+mul>m) return;
//当之后的数字已经没有0了，且要加上最小的数已超过m
dfs(w+1,sum+mul*num[last+1][w],w,1,ct+1,tot);
dfs(w+1,sum,w,mul*num[last+1][w],ct+1,tot);
dfs(w+1,sum,last,mul,ct,tot);
}
void work()
{
int l=0,r=n-1,mid,ans=-1;
while(l<=r)
{mid=(l+r)>>1;
tag=0;
dfs(1,0,0,1,0,mid);
if(tag) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
int main()
{
freopen("puzzle.in","r",stdin);
freopen("puzzle.out","w",stdout);
while(scanf("%s%d",ch+1,&m))
{if(m==-1) return 0;
n=strlen(ch+1);
pre(); work();
}
}