2014
01-05

# Dart Challenge

Clark and Harry are siblings. As they had been rivals since their early childhood, their father decided that both should concentrate on a different sport when they were thirteen. That way, they would not have to compete for success. Now both are twenty years old and excel in different fields: Clark plays chess while Harry participates in dart-tournaments.
Having won a series of three tournaments in a row, Harry started teasing Clark about not having as much success. Clark retorted that chess was less luck-based and thus more difficult. That offended Harry and led him to the reply that in order to play darts optimally, a lot of combinatorics are necessary. Clark returned an icy smile and the comment that memorizing all different late-games could hardly be called “combinatorics”.
This is how it came to the wager. Harry bets that he can find all possible late-games for generalized dart-boards where memorized late-games do not help him. When Clark showed him a list of possible dartboards, Harry had to admit that he probably bit off more than he can chew. As his friend, you have to help him!

A dart-board consists of different areas. Each area has an assigned score for hitting it. Each area also has a double- and a triple-field that are worth twice and three times the score of the area. The only exception is the area for the highest score: It has only a double- and no triple-field! Given the values of the different areas you have to find the number of possible scores that can be obtained with a given number of darts.

The inputs start with a line containing a single integer n. Each of the n following lines contains one test case. Each test case starts with two integers 1 <= a <= 100; 1 <= k <= 50, the number of different areas on the
dart-board and the number of darts. a integers 1 <= si <= 100 follow. si is the score for hitting area i. All scores are distinct. Remember that each area has a double- and, with exception of the area with the highest score, a triple-field. It is always possible to score 0 with any given dart by not hitting the board.

The inputs start with a line containing a single integer n. Each of the n following lines contains one test case. Each test case starts with two integers 1 <= a <= 100; 1 <= k <= 50, the number of different areas on the
dart-board and the number of darts. a integers 1 <= si <= 100 follow. si is the score for hitting area i. All scores are distinct. Remember that each area has a double- and, with exception of the area with the highest score, a triple-field. It is always possible to score 0 with any given dart by not hitting the board.

3
21 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25
2 2 20 10
1 50 1

Scenario #1:
172

Scenario #2:
9

Scenario #3:
101

#include<iostream>
#include<set>
#include<algorithm>
#include<stdio.h>
#include<cstring>
using namespace std;
int d[301];
int c[50001];
int e[50001];

bool cmp(const int x,const int y)
{
return x<y;
}

set<int> s;
int main()
{
int t;
scanf("%d",&t);
for(int l=1;l<=t;l++)
{
int a[101];
int p,k;
memset(c,0,sizeof(c));
memset(e,0,sizeof(e));
scanf("%d %d",&p,&k);
for(int i=1;i<=p;i++)
{
scanf("%d",&a[i]);
}

sort(a+1,a+p+1,cmp);

s.clear();
for(int i=1;i<=p;i++)
{
if(i!=p) {
s.insert(a[i]);
s.insert(a[i]*2);
s.insert(a[i]*3);
}
else
{
s.insert(a[i]);
s.insert(a[i]*2);
}
}

set<int>::iterator it,iy;
int i=0;
for(it=s.begin();it!=s.end();it++)
{
d[++i]=*it;
}
int ans=i;

e[0]=1;
c[0]=1;
for(int i=1;i<=k;i++)
{
for(int j=0;j<=d[ans]*k;j++)
for(int h=1;h<=ans;h++)
{
if(e[j]==1)
c[j+d[h]]=1;
}
for(int j=0;j<=d[ans]*k;j++)
{
e[j]=c[j];
}
}
int sum=0;
for(int j=0;j<=d[ans]*k;j++)
if(e[j]==1)
{
sum++;
}
printf("Scenario #%d:\n",l);
cout<<sum<<endl<<endl;

}
return 0;
}

1. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了