题目链接 2469: C 小Y的难题（1） Time Limit: 1000 MS Memory Limit: 65536 KB Total Submit: 9 Accepted: 7 Page View: 128 Submit Status Discuss Description
最近小Y迷上了数学，总是在思考各种数学问题。有一天，他不小心把墨水洒在草稿纸上。他现在能看到的是“2?3?1?4”（？表示看不清的地方）。小Y的记忆力不错，他知道： 1、每个？只会是“+”、“-”，“=”三个符号之一。 2、总共有且仅有一个“=”。 3、原式一定是一个等式。如“2+3-1=4” 现在他突然想知道，有多少种可能性，满足上面3个要求。 Input
多组输入。 每组第一行有一个数字n。表示小Y从左到右，一共可以看到n个数字。（2<=n<=15） 每组第二行有n个数字。分别表示这n个数字是什么。保证每个数字都是非负整数，且小于10^7。 Output
对于每组，输出一行，这一行只有一个数字，表示有多少种可能性满足题意。 Sample Input Raw 4 2 3 1 4 4 1 1 1 1 Sample Output Raw 2 6 Hint
数字之间一定有且仅有一个符号，第一个数字前没有符号。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int a[25]; int n; int ans=0; void DFS(int sum,int num,int c)//num表示要处理的第几个数 { if(num==n) { if(sum==0) ans+=c; return ; } DFS(sum+a[num], num+1, c); DFS(sum-a[num], num+1,c+1); } int main () { while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%d",&a[i]); ans=0; DFS(a[0],1,0); printf("%d\n",ans); } return 0; }