题解报告——购物券

购物券（bday）

时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】

小Y得到了两张价值不菲的SHOP购物券，所以他决定去买N件礼物送给朋友们。小Y选好了n件礼物，并且它们的价格之和恰好为两张购物券的面值之和。当小Y被自己的聪明所折服，高兴地去结账时，他突然发现SHOP对购物券的使用有非常奸诈的规定：一次只允许使用一张、不找零、不与现金混用。小Y身上根本没有现金，并且他不愿意放弃挑选好的礼物。这就意味着，他只能通过这两张购物券结账，而且每一张购物券所购买的物品的总价格必须精确地等于这张购物券的面额。怎样才能顺利地买回这n件礼物呢？你的任务就是帮助小Y确实是否存在一个购买方案。小Y会告诉你其中一张购物券的面额以及所有商品的价格，你只需要确定能否找到一种方案使得选出来的物品的价格总和正好是这张购物券的面额即可。

【输入】

输入有多组数据，每两行有一组数据。每组数据的第一行为两个整数n和m，分别表示小Y一共挑选了n个物品以及小Y的一张购物券的面额为m，接下来的一行有n个用空格隔开的正整数，第i个数表示第i物品的价格。

【输出】

输出包含若干行，每行一个单词"YES"或者"NO"，分别代表存在一个购买方案和不存在一个购买方案。

【输入样例】

10 2000
1000 100 200 300 400 500 700 600 900 800
10 2290
1000 100 200 300 400 500 700 600 900 800

【输出样例】

YES
NO

【提示】

对于30%的输入文件，所有的n≤20；

对于100%的输入文件，所有的n≤40，并且m和物品的总价值不超过 $2^{31} - 1$

【思路分析】

对于这样的数据其实我们是可以用一些优秀的暴力操过的，在这里我们只需要先dfs一半的物品，然后用哈希存一下，之后我们再dfs剩下的一半，每次只需要判断一下之前存储的一半，存不存在一个物品价值和，使加上当前价值后等于面额，注意这里说是有两张购物券，其实就是废话，只需要处理一张购物券即可。。。

【代码实现】

 1 #include<cstdio>
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 const int mod=1e5+7;
 6 vector<int> hash[mod+2];
 7 int money[75];
 8 int n,m;
 9 bool flag;
10 void dfs(int v,int mm)
11 {
12     if(mm==m) {flag=true;return;}
13     int m1=(mm%mod+mod)%mod;
14     hash[m1].push_back(mm);
15     if(v==n/2)
16         return;
17     if(mm+money[v+1]<=m)
18     dfs(v+1,mm+money[v+1]);
19     dfs(v+1,mm);
20 }
21 bool dfs2(int v,int mm)
22 {
23     if(v==n+1) return false;
24     int m1=((m-mm)%mod+mod)%mod;
25     int ss=hash[m1].size();
26     for(int i=0;i<ss;i++)
27     {
28         if(mm+hash[m1][i]==m)
29         return true;
30     }
31     bool ac;
32     if(mm+money[v+1]<=m)
33     {
34         ac=dfs2(v+1,mm+money[v+1]);
35         if(ac) return true;
36     }
37     ac=dfs2(v+1,mm);
38     if(ac) return true;
39     return false;
40 }
41 int main()
42 {
43     while(scanf("%d%d",&n,&m)!=EOF)
44     {
45         flag=false;
46         for(int i=0;i<=mod+1;i++)
47         hash[i].clear();
48         for(int i=1;i<=n;i++)
49         scanf("%d",&money[i]);
50         dfs(0,0);
51         if(flag==true)
52         {printf("YES
");continue;}
53         if(dfs2(n/2,0))
54         printf("YES
");
55         else
56         printf("NO
");
57     }
58     return 0;
59 }