从描述中看出，非前缀且权值和最小，于是我想到了哈夫曼编码。类似的，对于这道题，我们可以考虑建立一个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