http://acm.hdu.edu.cn/showproblem.php?pid=2266
给一个字符串和一个数n,在字符串中间可以插入+或者 -,问有多少种等于n的情况.
要注意任意两个数之间都可以插入也可以不插入,注意枚举完所有情况.
#include <cstdio>
#include <cstring>
char s[];
int n,l,cnt; void dfs(int k,int sum)
{
if(k==l)
{
if(sum==n) cnt++;
return;
}
long long ans=;
for(int i=k;i<l;i++)
{
ans=ans*+s[i]-'';
dfs(i+,sum+ans);
if(k!=) dfs(i+,sum-ans);
}
}
int main()
{
//freopen("a.txt","r",stdin);
while(~scanf("%s",s))
{
scanf("%d",&n);
//printf("%s %d\n",s,n);
l=strlen(s);
cnt=;
dfs(,);
printf("%d\n",cnt);
}
return ;
}