区间DP 哈夫曼树

使得任何一个单词的编码（对应的 01 串）不是另一个单词编码的前缀

看到这句话自然想到哈夫曼编码（想出用哈夫曼树解决是关键），但是题干下面又说了

$a_1,a_2,…,a_n$ 的编码是按字典序升序排列的

这说明$a_1,a_2,…,a_n$需要按升序的顺序作为叶子节点出现在树中，既然$n$个数的位置固定了我们就可以区间DP来解决这个哈夫曼树问题。

经典哈夫曼树问题可以参考:148. 合并果子 (这道题目是直接用堆来解决，因为果子的位置随意)
区间DP可以参考这题：282. 石子合并(这道题是裸区间DP)

虽然说这道题的代码跟282. 石子合并的一毛一样，但是没有哈夫曼编码的前导知识可能连题目都读不懂。

#include <iostream>

using namespace std;

const int N = 1010;

int n , s[N];//利用前缀和快速求出合并若干个点的花费
int f[N][N];//f[l][len]表示合并的长度为len，且左端点为l的区间所需要的花费

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)   cin >> s[i] , s[i] += s[i - 1];

    for(int len = 1 ; len <= n ; len++)//枚举区间长度
        for(int l = 1 ; l + len - 1 <= n ; l++)//枚举左端点
        {
            int r = l + len - 1;//计算右端点
            if(len == 1) f[l][r] = 0;//如果区间长度为1不用合并
            else
            {
                f[l][r] = 0x3f3f3f3f;
                for(int k = l ; k < r ; k++)//枚举合并分界点
                    f[l][r] = min(f[l][r] , f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }

    cout << f[1][n] << endl;
}