哈夫曼树

总结

构建

每次选值（出现次数）最小的两个数，为他们构建一个共同的父结点，结点值为两数值之和。
然后不断地进行下去。

编码

从上往下，把左儿子路径标为$0$,右儿子路径标为$1$。
每个叶子结点的编码为从叶子结点到根结点的标号字符串。

性质

• 值越大（出现次数越多）就离根结点越近。
• 每个叶子结点编码互不为前缀。

应用

• 可以应用哈夫曼编码来表示一些互不为前缀的东西（如字符串）。
• [NOI2015]荷马史诗
• 已知每个互不为前缀的字符串的出现次数，询问哈夫曼树点数。

据说设$dp[i][j][k]$表示第$i$层，当前层还有$j$个空结点，下一层还有$k$个空结点是否作为终止结点即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=800;
int n,dp[2][N][N],s[N],a[N];
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il bool cmp(re int x,re int y){return x>y;}
int main()
{
  freopen("epic.in","r",stdin);
  freopen("epic.out","w",stdout);
  n=gi();
  fp(i,1,n) a[i]=gi();sort(a+1,a+1+n,cmp);
  fq(i,n,1) s[i]=s[i+1]+a[i];
  re int now=0,nxt=1;
  memset(dp[now],127,sizeof(dp[now]));
  dp[now][1][0]=0;
  fp(i,0,n)
  {
    swap(now,nxt);
    memset(dp[now],127,sizeof(dp[now]));
    fp(j,0,n-i)
      fp(k,0,n-i-j)
      {
    if(dp[nxt][j][k]>2e9) continue;
        if(j) dp[now][j-1][k]=min(dp[now][j-1][k],dp[nxt][j][k]);
    dp[nxt][j+k][j]=min(dp[nxt][j+k][j],dp[nxt][j][k]+s[i+1]);
      }
  }
  printf("%d\n",dp[nxt][0][0]);    
  fclose(stdin);
  fclose(stdout);
  return 0;
}