题目看了半小时才看懂的。
题意：首先根据给出的序列，构造出哈夫曼树，构造出来的是一棵二叉树，每个节点都有一个权值，每个节点的两个儿子只能取一个，问能否使取出来的节点权值之和刚好等于e。
这样一分析就很容易看出是01背包。但是，背包容量特别大！不能纯粹的用循环做背包肯定会超时。可以使用两个队列存能够凑出来的数字（相当于滚动数组的作用），还有一个优化，看当前要压入队列的数字是否已经在队列中，这个可以用map存一下。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
using namespace std; const int maxn=;
int s;
long long e;
long long f[maxn];
struct X
{
long long a,b;
} u[maxn];
int Size,cnt;
map<long long,bool>flag; struct cmp
{
bool operator ()(long long &a,long long &b)
{
return a>b;
}
}; int main()
{
int T; scanf("%d",&T);
while(T--)
{
flag.clear();
scanf("%d",&s);
cnt=;
priority_queue<long long,vector<long long>,cmp>q;
for(int i=; i<=s; i++)
{
scanf("%lld",&f[i]);
q.push(f[i]);
}
scanf("%lld",&e);
Size=s;
while(Size!=)
{
u[cnt].a=q.top();
q.pop();
Size--;
u[cnt].b=q.top();
q.pop();
Size--;
q.push(u[cnt].a+u[cnt].b);
cnt++;
Size++;
} queue<long long>Q1;
queue<long long>Q2;
int f=;
Q1.push(u[].a);
Q1.push(u[].b); for(int i=; i<cnt; i++)
{
flag.clear();
if(f==)
{
while(!Q1.empty())
{
if(Q1.front()+u[i].a<=e&&flag[Q1.front()+u[i].a]==){
Q2.push(Q1.front()+u[i].a);
flag[Q1.front()+u[i].a]=;
}
if(Q1.front()+u[i].b<=e&&flag[Q1.front()+u[i].b]==){
Q2.push(Q1.front()+u[i].b);
flag[Q1.front()+u[i].b]=;
}
Q1.pop();
}
f=;
}
else
{
while(!Q2.empty())
{
if(Q2.front()+u[i].a<=e&&flag[Q2.front()+u[i].a]==){
Q1.push(Q2.front()+u[i].a);
flag[Q2.front()+u[i].a]=;
}
if(Q2.front()+u[i].b<=e&&flag[Q2.front()+u[i].b]==){
flag[Q2.front()+u[i].b]=;
Q1.push(Q2.front()+u[i].b);
}
Q2.pop();
}
f=;
}
} bool ans=; if(f==)
{
while(!Q1.empty())
{
if(Q1.front()==e) ans=;
Q1.pop();
}
}
else
{
while(!Q2.empty())
{
if(Q2.front()==e) ans=;
Q2.pop();
}
} if(ans) printf("Yes\n");
else printf("No\n");
}
return ;
}