ZOJ 3931 Exact Compression

 题目看了半小时才看懂的。

题意：首先根据给出的序列，构造出哈夫曼树，构造出来的是一棵二叉树，每个节点都有一个权值，每个节点的两个儿子只能取一个，问能否使取出来的节点权值之和刚好等于e。

这样一分析就很容易看出是01背包。但是，背包容量特别大！不能纯粹的用循环做背包肯定会超时。可以使用两个队列存能够凑出来的数字（相当于滚动数组的作用），还有一个优化，看当前要压入队列的数字是否已经在队列中，这个可以用map存一下。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;

const int maxn=200;
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=0;
        priority_queue<long long,vector<long long>,cmp>q;
        for(int i=1; i<=s; i++)
        {
            scanf("%lld",&f[i]);
            q.push(f[i]);
        }
        scanf("%lld",&e);
        Size=s;
        while(Size!=1)
        {
            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=0;
        Q1.push(u[0].a);
        Q1.push(u[0].b);

        for(int i=1; i<cnt; i++)
        {
            flag.clear();
            if(f==0)
            {
                while(!Q1.empty())
                {
                    if(Q1.front()+u[i].a<=e&&flag[Q1.front()+u[i].a]==0){
                        Q2.push(Q1.front()+u[i].a);
                        flag[Q1.front()+u[i].a]=1;
                    }
                    if(Q1.front()+u[i].b<=e&&flag[Q1.front()+u[i].b]==0){
                        Q2.push(Q1.front()+u[i].b);
                        flag[Q1.front()+u[i].b]=1;
                    }
                    Q1.pop();
                }
                f=1;
            }
            else
            {
                while(!Q2.empty())
                {
                    if(Q2.front()+u[i].a<=e&&flag[Q2.front()+u[i].a]==0){
                        Q1.push(Q2.front()+u[i].a);
                        flag[Q2.front()+u[i].a]=1;
                    }
                    if(Q2.front()+u[i].b<=e&&flag[Q2.front()+u[i].b]==0){
                        flag[Q2.front()+u[i].b]=1;
                        Q1.push(Q2.front()+u[i].b);
                    }
                    Q2.pop();
                }
                f=0;
            }
        }

        bool ans=0;

        if(f==0)
        {
            while(!Q1.empty())
            {
                if(Q1.front()==e) ans=1;
                Q1.pop();
            }
        }
        else
        {
            while(!Q2.empty())
            {
                if(Q2.front()==e) ans=1;
                Q2.pop();
            }
        }

        if(ans) printf("Yes
");
        else printf("No
");
    }
    return 0;
}