2017年上海金马五校程序设计竞赛 Problem C : Count the Number

Problem C : Count the Number

Time Limit: 3 s

Description

Given n numbers, your task is to insert ‘+’ or ‘-’ in front of each number to construct expressions. Note that the position of numbers can be also changed. You can calculate a result for each expression. Please count the number of distinct results and output it.

Input

There are several cases. For each test case, the first line contains an integer n (1 ≤ n ≤ 20), and the second line contains n integers a1,a2, … ,an (-1,000,000,000 ≤ ai ≤ 1,000,000,000).

Output

For each test case, output one line with the number of distinct results.

Sample Input

2 1 2 3 1 3 5

Sample Output

4 8

---

分析

题意：给一组数，每个数字前需要加一个“+”或者一个“-”，最后将全部数求和，计算出各种情况的下总和的值不同的数目。很简单，时间限制3s，所以直接暴力

代码

#include <algorithm> #include <iostream> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int a[22],b[2000000]; int N,sum,sumn1; void counth(int i,queue<int>q) { if(i>=N)///全部数都加上之后计算不同的和的数量 { int zsum; zsum=q.size(); sum=zsum; for(int k=0;k<zsum;k++) { b[k]=q.front(); q.pop(); }///将队列中的元素存入数组中 sort(b,b+zsum);///将数组元素排序用来删重 for(int k=1;k<zsum;k++) if(b[k]==b[k-1])sum--; return; } sumn1=q.size(); for(int j=0;j<sumn1;j++) { q.push(q.front()+a[i]);///将各个数字的两种情况都入队 q.push(q.front()-a[i]); q.pop();///将计算过的总和出队 } i++; counth(i,q); } int main() { while(~scanf("%d",&N)) { queue<int>q;///定义队列存放不同情况下的和 for(int k=0;k<N;k++) scanf("%d",&a[k]); q.push(a[0]); q.push(-a[0]);///将第一个数入队 counth(1,q); printf("%d\n",sum); } }