acdream 1726 A Math game（部分和）

迈不过友情╰ 2022-06-05 23:51 162阅读 0赞

### A Math game ###

Time Limit:  2000/1000MS (Java/Others)     Memory Limit:  256000/128000KB (Java/Others)

Submit  [Status][]

#### Problem Description ####

Recently, Losanto find an interesting Math game. The rule is simple: Tell you a number  H, and you can choose some numbers from a set \{a\[1\],a\[2\],......,a\[n\]\}.If the sum of the number you choose is  H, then you win. Losanto just want to know whether he can win the game.

#### Input ####

There are several cases.  
In each case, there are two numbers in the first line  n (the size of the set) and  H. The second line has n numbers \{a\[1\],a\[2\],......,a\[n\]\}. 0<n<=40, 0<=H<10^9, 0<=a\[i\]<10^9,All the numbers are integers.

#### Output ####

If Losanto could win the game, output "Yes" in a line. Else output "No" in a line.

#### Sample Input ####

10 87
    2 3 4 5 7 9 10 11 12 13
    10 38
    2 3 4 5 7 9 10 11 12 13

#### Sample Output ####

No
    Yes

思路：求部分和，用DFS，对于每一个数，选或者不选， 需要剪枝。

#include<cstdio>
    using namespace std;
    const int maxn=50;
    int num[maxn], n, m;
    long  long sum[maxn];
    
    int DFS(long long s, int pos)
    {
        if(s==m)
            return 1;
        if(sum[n]-sum[pos-1]+s<m || pos>n || s>m)
            return 0;
        if(DFS(s+num[pos], pos+1))
            return 1;
        if(DFS(s, pos+1))
            return 1;
        return 0;
    }
    
    int main(){
        while(~scanf("%d%d", &n, &m))
        {
            for(int i=1; i<=n; i++)
            {
                scanf("%d", num+i);
                sum[i]=sum[i-1]+num[i];
            }
            if(DFS(0, 1))
                printf("Yes\n");
            else
                printf("No\n");
        }
        return 0;
    }

[Status]: http://acdream.info/contest?cid=1477#status--E