BZOJ2923 [Poi1998]The lightest language

题面在这里

​

想象一棵Trie树，就是要选n个权值最小的点，使得任意两点不存在祖先关系

然后维护每个叶子节点，往下扩展即可

实际操作时不用真的维护每个叶子结点，取其前n小的即可

得不到更优解时停止

​

示例程序：

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;

const int maxn=10005;
int n,K,w[30],sum,ans;
multiset<int> S;
typedef set<int>::iterator iter;
int main(){
	scanf("%d%d",&n,&K);
	for (int i=1;i<=K;i++) scanf("%d",&w[i]),S.insert(w[i]),sum+=w[i];
	ans=0x7fffffff;
	while (1){
		if (S.size()>=n){
			if (sum>=ans) break;else ans=sum;
		}
		int x=*S.begin();S.erase(S.begin());sum-=x;
		for (int i=1;i<=K;i++)
		 S.insert(x+w[i]),sum+=x+w[i];
		while (S.size()>n) sum-=*(--S.end()),S.erase(--S.end());
	}
	printf("%d",ans);
	return 0;
}