题目描述
哈夫曼树常用于解决最优编码问题：即给定若干种不同字符在文本中的出现次数（频率），试为每个字符给出一个 01 串作为编码，使得 $\text{频率}\times\text{码长}$ 之和最小，且没有任何一个编码是另一个编码的前缀。
本题中，需要解决的是一个非常类似的问题：按字典序从小到大，给出 $n$ 种不同字符及其频率，试为每个字符给出一个 $k$ 进制字符串（即，字符串中的每个字符为 $0\sim k-1$ 中的一个）作为编码，使得 $\text{频率}\times\text{码长}$ 之和最小，且没有任何一个编码是另一个编码的前缀。同时，你还需要保证给出的编码在字典序上是保序的，即，不会出现两个字符 $a,b$，使得字典序上 $a$ 比 $b$ 小，但是 $a$ 的编码比 $b$ 的编码的字典序大。
只需输出最小的 $\text{频率}\times\text{码长}$ 之和即可。
输入格式
第一行两个正整数 $n,k$，含义如题面中所述。
第二行 $n$ 个正整数 $a_1,a_2\ldots,a_n$，其中 $a_i$ 表示字典序第 $i$ 小的字符的频率。
输出格式
输出一个整数，表示答案。
样例输入1
6 2
1 4 5 4 1 5样例输出1
50样例输入2
15 3
5 6 8 10 7 3 6 6 9 5 9 6 6 1 4样例输出2
227样例3、4
见下发文件。
数据范围
对于所有数据，$2\le n\le 500;2\le k\le 60;a_i \le 10^9$。
| 测试点编号 | $n\le$ | $k\le$ |
|---|---|---|
| $1\sim 3$ | $10$ | $5$ |
| $4\sim 5$ | $60$ | $10$ |
| $6\sim 8$ | $500$ | $10$ |
| $9\sim 10$ | $500$ | $60$ |
发现在哈夫曼树的一棵子树所代表的那些数，对应出来一定是原序列的一个区间。所以考虑区间dp.
定义 \(dp_{l,r,k}\) 为现在递归到区间 \([l,r]\)，有 \(k\) 个叶子节点可以填的情况。发现所谓有 \(k\) 个叶子可以填，其实就是把这个区间分成 \(k\) 份。定义 \(dp_{l,r,i}\) 表示把这个区间分成 \(i\) 份后的价值和，然后 \(dp_{l,r,1}=dp_{l,r,k}+s_r-s_{l-1}\)。最终答案为 \(dp_{1,n,1}\)。
发现对于每一个区间，我们只需要 \(dp_{l,r,1}\) 和 \(dp_{l,r,k}\) 的值。而 \(dp_{l,r,l}\) 可以用一个倍增之类的东西求出来。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=505;
int n,k,v[N],t[N],idx;
LL s[N],a[N],dp[N][N][16];
void dfs(int x)
{
if(t[x])
return;
if(x==1)
return;
v[++idx]=x,t[x]=idx;
dfs(x/2);
dfs((x+1)/2);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",a+i),s[i]=s[i-1]+a[i];
dfs(k);
// for(int i=1;i<=n;i++)
// dp[i][i][t[1]]=a[i];
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
memset(dp[i][j],0x3f,sizeof(dp[i][j]));
for(int p=1;p<=idx;p++)
{
if(v[p]==1)
continue;
int lc=t[v[p]/2],rc=t[v[p]-v[p]/2];
for(int l=i-1;l<=j;l++)
dp[i][j][p]=min(dp[i][j][p],dp[i][l][lc]+dp[l+1][j][rc]);
// printf("%d %d %d %d\n",i,j,v[p],dp[i][j][p]);
}
dp[i][j][t[1]]=dp[i][j][t[k]]+s[j]-s[i-1];
}
}
printf("%lld",dp[1][n][t[1]]);
}