这是一道比赛时的题目，但由于我没报名，所以浪费了一个大好的切水题的机会。
是经典的meet in middle（折半搜索）的模板题，但是之前一直没找到这种题目，今天终于看到了。
由于m的范围极大，因此一般的背包DP是行不通的。
如果直接进行2^n的爆搜，也只有40分。
所以这里我们观察数据n=40，发现如果是2^(n/2)，就可以像前面一样跑过去。
所以我们缩小范围，先在1到n/2的范围内找出所有m以内的价值的和，用hash来存（这里需要挂链）；
然后同样的在n/2+1到n的范围内找出所有m以内的价值的和，接着通过hash查询是否存在m-tot，如果有说明有解可以退出。
这应该是meet in middle的最简单的合并两部分的方式了吧。
需要注意的是hash的时候直接%一个数就可以了，不用乘来乘去浪费时间（我就是这样TLE了好几次），通过挂链来实现查询。
具体实现看代码CODE
#include<cstdio> #include<cstring> using namespace std; const int N=45,mod=2333333; struct egde { int v,next; }link[(1<<20)+10]; int head[mod],a[N],n,m,k; bool h[mod],flag; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void add(int x,int y) { link[++k].v=y; link[k].next=head[x]; head[x]=k; } inline int hash(int k) { return k%mod; } inline void init(int k,int tot) { if (flag) return; if (tot==m) { flag=1; return; } if (k>n/2) { int t=hash(tot); h[t]=1; add(t,tot); return; } if (tot+a[k]<=m) init(k+1,tot+a[k]); init(k+1,tot); } inline void DFS(int k,int tot) { if (flag) return; if (k>n) { int now=hash(m-tot); if (!h[now]) return; for (register int i=head[now];i!=-1;i=link[i].next) if (link[i].v==m-tot) { flag=1; break; } return; } if (tot+a[k]<=m) DFS(k+1,tot+a[k]); DFS(k+1,tot); } int main(void) { register int i; while (scanf("%d%d",&n,&m)!=EOF) { memset(h,0,sizeof(h)); memset(link,-1,sizeof(link)); memset(head,-1,sizeof(head)); for (i=1;i<=n;++i) read(a[i]); k=flag=0; init(1,0); if (flag) { puts("YES"); continue; } DFS(n/2+1,0); puts(flag?"YES":"NO"); } return 0; }