[关闭]
@Chilling 2017-01-16T16:19:15.000000Z 字数 860 阅读 1013

swustoj-2469: C 小Y的难题(1)

搜索


Description

最近小Y迷上了数学,总是在思考各种数学问题。有一天,他不小心把墨水洒在草稿纸上。他现在能看到的是“2?3?1?4”(?表示看不清的地方)。小Y的记忆力不错,他知道:
1、每个?只会是“+”、“-”,“=”三个符号之一。
2、总共有且仅有一个“=”。
3、原式一定是一个等式。如“2+3-1=4”
现在他突然想知道,有多少种可能性,满足上面3个要求。

Input

多组输入。
每组第一行有一个数字n。表示小Y从左到右,一共可以看到n个数字。(2<=n<=15)
每组第二行有n个数字。分别表示这n个数字是什么。保证每个数字都是非负整数,且小于

Output

对于每组,输出一行,这一行只有一个数字,表示有多少种可能性满足题意。

Sample Input

4
2 3 1 4
4
1 1 1 1

Sample Output

2
6

Hint

数字之间一定有且仅有一个符号,第一个数字前没有符号。

  1. #include<stdio.h>
  2. #include<string.h>
  3. int a[22],ans,n;
  4. void dfs(int sum,int s,int count)//sum表示整个式子的和,s判断是否包含了n个数(位数),count表示减号的个数
  5. {
  6. if(s>n)//如果s>n则表示所有数都被涵盖了
  7. return;
  8. if(sum==0&&s==n)//sum=0成立的式子当中有几个减号就有几种两边相等的情况,可举例证明
  9. ans+=count;
  10. dfs(sum+a[s],s+1,count); //加上下一个数,减号个数count不变
  11. dfs(sum-a[s],s+1,count+1); //减去下一个数,减号个数++
  12. }
  13. int main()
  14. {
  15. int i;
  16. while(scanf("%d",&n)!=EOF)
  17. {
  18. memset(a,0,sizeof(a));
  19. ans=0;
  20. for(i=0;i<n;i++)
  21. scanf("%d",&a[i]);
  22. dfs(a[0],1,0);
  23. printf("%d\n",ans);
  24. }
  25. return 0;
  26. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注