本文正體字版由OpenCC轉換
從描述中看出，非前綴且權值和最小，於是我想到了哈夫曼編碼。類似的，對於這道題，我們可以考慮建立一個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
上次修改時間 2017-02-03