「NOIP模拟赛」狐狸的谜语
题目描述
话说某一个月黑风高的晚上,一只褐色的狐狸快速地跳过了一只懒狗,并留下一个字符串“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
还可以迭代深搜或者二分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char a[25]; int len,t,deep,v[25][25]; bool flag,b[25]; void pre() { for(int i=len;i;i--) if(a[i]=='0') { while(i--)b[i]=0; break; } else b[i]=1; for(int i=1;i<=len;i++) for(int j=i;j<=len;j++) { v[i][j]=v[i][j-1]*10+a[j]-'0'; v[i][j]=min(v[i][j],t+1); } } void dfs(int x,int k,int last,int mul,int sum) { if(sum>t||flag||k>deep)return; if(x==len) { if(sum+mul*v[last+1][len]==t)flag=1; else return; } if(b[x-1]&&sum+mul>t)return; dfs(x+1,k+1,x,1,sum+mul*(v[last+1][x])); dfs(x+1,k+1,x,mul*(v[last+1][x]),sum); dfs(x+1,k,last,mul,sum); } void solve() { pre(); int ans=-1; int l=0,r=len-1; while(l<=r) { deep=(l+r)>>1; flag=0; dfs(1,0,0,1,0); if(flag)ans=deep,r=deep-1; else l=deep+1; } printf("%d\n",ans); } int main() { while(scanf("%s%d",a+1,&t)) { if(t==-1)return 0; len=strlen(a+1); solve(); } return 0; } |
Subscribe
计数器 9774906
OI 课件=>
OI 课件=>