本题大意：
使用 01 串为单词编码，要求：
1、编码使用前缀码，即任何一个单词的编码不是另一个单词编码的前缀；
2、编码需要按字典序升序排列，比如 \(C\) 的编码的字典序需要 \(D\) 的编码之前。
请找出一种字典序编码，使得文字经过编码后的长度 \(L\) 最小，输出最小长度。
原题链接：3240. 压缩编码 - AcWing
本题关键点： 字典序需要按顺序合并，等价于只能合并相邻的两个点[1]。
而哈夫曼树选取的是最小的两个数，位置是随机选取的，所以本题应该采用区间DP。
代码同：AcWing 282. 石子合并 - haruhomu
时间复杂度：\(O(n^3)\)
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n;
int s[N]; //前缀和
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1];
}
//枚举区间长度len，若len=1，则不需要付出合并代价
for (int len = 2; len <= n; len++) {
//枚举起点i，从i开始的len长度区间不能超过n
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1; //终点j
f[i][j] = 1e8;
//枚举分界点k，范围为[i,j-1]
for (int k = i; k < j; k++)
//s[j]-s[i-1] 代表合并[i,k] [k+1,j] 的代价
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
cout << f[1][n];
}