首页 > ACM题库 > HDU-杭电 > hdu 2386 Dart Challenge[解题报告]C++
2014
01-05

hdu 2386 Dart Challenge[解题报告]C++

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. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了