This post is written in Chinese. Please consider using Google Translate

从描述中看出，非前缀且权值和最小，于是我想到了哈夫曼编码。类似的，对于这道题，我们可以考虑建立一个k叉树，这个树的每个叶节点代表一个字符串，只须找出最小的n个叶节点的权值，就是结果。

首先建立一个0节点，在此基础上首先加入每个单个字母，当叶节点的个数不足n个时，取出最小的一个节点，对这个节点进行扩展，即把它的权值分别加上每个字母的权值，作为新的k个叶节点。否则把前n小的节点取出，计算它们的权值之和。如果这个和小于当前已知最优解，更新最优解，否则结束，因为再扩展一定不会比当前值小。

实际上我们并不需要建立树结构，只需要对叶节点的权值抽象的维护。首先把每个字母的权值插入优先队列，每次取出前n小的值计算，并以最小值来维护。

一般情况下我们用最小堆实现优先队列，但是堆中可能会存在n^2个元素，大大超过了空间限制。但是优先队列中只有前n小的元素是对我们有用的，我们可以以此改进堆，只存储前n小的元素。当插入一个新的元素时，把堆中的最大值删除，这样维护的一定是前n小的。这样又会带来新的问题，在最小堆中取最大值是O(n)时间复杂度的。于是必须同时维护一个最大堆，使取删最大值变为O(logn)。需要同时维护两个堆，在每个元素之间建立映射关系，每次删除都要对两个堆进行维护。

这样虽然可以解决问题，但是会大大增加编程的复杂度，可以考虑不用堆来维护。我用了更强大的数据结构，平衡树。平衡树在插入、取最大、取最小、删除上均有O(logn)的时间复杂度，使用平衡树可以使编程思路更清晰。我用的是Treap。

以下是我用Treap实现的代码。

/* 
 * Problem: POI1998 naj
 * Author: Guo Jiabao
 * Time: 2008.12.3 20:03:22
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

class tTreap
{
    public:
        class tNode
        {
            public:
                int v,fix;
                tNode *l,*r;
                tNode(int tv,tNode *nl): v(tv),l(nl),r(nl)
                {
                    fix=rand();
                }
        };
        tNode *root,*null;
        int sum,size,lim;
        tTreap()
        {
            root=null=new tNode(0,0);
            sum=0;
        }
        void rot_r(tNode *&p)
        {
            tNode *q=p->l;
            p->l=q->r;
            q->r=p;
            p=q;
        }
        void rot_l(tNode *&p)
        {
            tNode *q=p->r;
            p->r=q->l;
            q->l=p;
            p=q;
        }
        void _ins(tNode *&p,int v)
        {
            if (p==null)
            {
                p=new tNode(v,null);
            }
            else if (v <= p->v)
            {
                _ins(p->l,v);
                if (p->l->fix < p->fix)
                    rot_r(p);
            }
            else
            {
                _ins(p->r,v);
                if (p->r->fix < p->fix)
                    rot_l(p);
            }
        }
        void ins(int v)
        {
            _ins(root,v);
            size++;
            sum+=v;
            if (size>lim)
                delmax();
        }
        int _delmin(tNode *&p)
        {
            if (p->l==null)
            {
                int v=p->v;
                tNode *t=p;
                p=p->r;
                delete t;
                return v;
            }
            else
            {
                return _delmin(p->l);
            }
        }
        int _delmax(tNode *&p)
        {
            if (p->r==null)
            {
                int v=p->v;
                tNode *t=p;
                p=p->l;
                delete t;
                return v;
            }
            else
            {
                return _delmax(p->r);
            }
        }
        int delmin()
        {
            size--;
            int r=_delmin(root);
            sum-=r;
            return r;
        }
        int delmax()
        {
            size--;
            int r=_delmax(root);
            sum-=r;
            return r;
        }
};

const int MAXK=30;
const int INF=0x7FFFFFFF;

tTreap T;
int W[MAXK];
int N,K,Ans;

void init()
{
    int i;
    freopen("naj.in","r",stdin);
    freopen("naj.out","w",stdout);
    scanf("%d%d",&N,&K);
    T.lim=N;
    for (i=1;i<=K;i++)
    {
        scanf("%d",&W[i]);
        T.ins(W[i]);
    }
    Ans=INF;
}

void solve()
{
    int i,A;
    while (T.sum<Ans)
    {
        if (T.size>=N)
        {
            if (T.sum<Ans)
                Ans=T.sum;
            else
                break;
        }
        A=T.delmin();
        for (i=1;i<=K;i++)
        {
            T.ins(A+W[i]);

        }
    }
}

int main()
{
    init();
    solve();
    printf("%d",Ans);
    return 0;
}

<h2><span class="mw-headline">最轻的语言</span></h2>

字母表AK由英文字母表的大写字母K组成。一个被称作重量的正整数被委派给字母表的每一个字母。一个由字母表AK的字母组成的字符串的重量是这个字 符串的所有字母的总重量。一个基于字母表AK的语言由这个字母表的字母组成的字符串的有限集合。一个语言的重量是所有它的字符串的重量之和。如果这个语言 的任意两个字符串W、V，W不是V的前缀，那我们说这个语言不是前缀的。

我们想找出基于字母表AK的N个要素的非前缀语言的可能的最小重量。

例如

假设K=2，字母a的重量W（a）=2 字母b的重量W（b）=5。字符串ab的重量W（ab）=2+5=7。 W（aba）=2+5+2=9。语言J={ab，aba，b}的重量-W（J）=21。语言J不是非前缀，因为字符串ab是aba的前缀。基于字母表A2最轻的三元非前缀语言（假设字母的重量如前）是{b，aa，ab}；它的重量是16。

任务

写一个程序：

• 从文本文件中读取两个整数n，k和字母表Ak 的k个字母的重量；
• 计算基于字母表Ak 的非前缀的n元语言的最小重量；

• 把结果写到文本文件。

  输入

  在输入文件的首行有两个被空格号分开的正整数n、k(2<=n<=10000, 2<=k<=26)。它们是语言中的字符串数和字母表中各个字母数。第二行包括被空格号隔开的k个正整数。每一个都不大于10000。第I个数是第I个字母的重量。

  输出

  在输出文件的首行应该写一个整数-基于字母表Ak 的最轻的非前缀的n元语言重量。

  样例输入

  3 2
    2 5

  样例输出

  16