15分开始 理解题意-

不能互作前缀的01编码就是trie树中的叶子节点
节点的数量就是trie树中节点的深度,节点的大小是trie树中节点的值

同时我们可以发现，最优解(每个叶子节点的深度尽可能小)时一定是完全二叉树(每个节点要么没有儿子，要么两个儿子)

目标：将$1 \sim n$转化成一颗二叉树使得总编码长度最小

则取点$i$为根节点时，由于要按字典序排所有点,$[1.i-1]$在根节点的左子树，$[i+1,n]$在根节点的右子树,那么剩下的问题就是递归的将左区间$[1.i-1]$和右区间$[i+1,n]$变为haffman树

则原问题变成若干个子问题-每个子问题用一个状态表示

状态表示

$f[i][j]:将原序列里的[i,j]变成一颗trie树的最优解的总长度$

状态转移

子集左边1个,右边n-1个|左边2个,右边n-2个|...|左边n-1个,右边1个

$$ 第k个节点作为根节点的haffman树 \\\\f[i]\[k](左子树长度)+f[k+1]\[j](右子树长度)+\\\\ \sum_i^{j} a_{t}(左右子树挂在节点k下后两个区间中的每个点都增加1,同时加入第k个节点a_k)$$
$$f[i]\[j]=f[i]\[k]+f[k+1]\[j]+\sum_i^{j} a_{t}$$

复杂度$O(n^3)$
$选i,j,k3个点,C_{1000}^{3}$
四边形不等式优化$O(n^2)$
贪心优化$O(nlog(n))$

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1010;

int n;
int s[N],f[N][N];

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    // 区间长度为1时,构成的树没有边--所以距离是0，编码长度=0,所以直接从长度2开始枚举
    for(int i=n-1;i>=0;i--)//枚举区间左端点
        for(int j=i+1;j<=n;j++)//枚举区间右端点
        {
            f[i][j]=1e9;
            for(int k=i;k<j;k++)//枚举区间[i,j]的根节点
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    cout<<f[1][n];
    return 0;
}