程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> acdream 1726 A Math game (部分和問題 DFS剪枝)

acdream 1726 A Math game (部分和問題 DFS剪枝)

編輯:關於C++

 

A Math game

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

Problem Description

Recently, Losanto find an interesting Math game. The rule is simple: Tell you a numberH, and you can choose some numbers from a set {a[1],a[2],......,a[n]}.If the sum of the number you choose isH, 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) andH. The second line has n numbers {a[1],a[2],......,a[n]}.0,All the numbers areintegers.

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

Source

第九屆北京化工大學程序設計競賽

題目鏈接:http://acdream.info/problem?pid=1726

題目大意:部分和問題

題目分析:正解是二分+DFS,我的做法是DFS用前綴和剪枝,4ms過,估計還是數據水了,

#include 
#include 
#define ll long long
ll a[45], h, sum[45];
int n;
bool flag;
 
void DFS(ll num, int pos)
{
    if(num == h)
    {
        flag = true;
        return;
    }
    if(flag || pos == n + 1)  
        return;
    //若當前數字加剩下的數字和小於h或者當前數字大於h則返回
    //不加妥T
    if(sum[n] - sum[pos - 1] + num < h || num > h) 
        return;
    DFS(num + a[pos], pos + 1);
    DFS(num, pos + 1);
    return;
}
 
int main()
{
    while(scanf("%d %lld", &n, &h) != EOF)
    {
        memset(sum, 0, sizeof(sum));
        flag = false;
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        DFS(0, 1);
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved