從描述中看出，非前綴且權值和最小，於是我想到了哈夫曼編碼。類似的，對於這道題，我們可以考慮建立一個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