本题大意:
使用 01 串为单词编码,要求:
1、编码使用前缀码,即任何一个单词的编码不是另一个单词编码的前缀;
2、编码需要按字典序升序排列,比如 $C$ 的编码的字典序需要 $D$ 的编码之前。
请找出一种字典序编码,使得文字经过编码后的长度 $L$ 最小,输出最小长度。
3240. 压缩编码 - AcWing - Tag:区间DP、哈夫曼树
本题关键点: 字典序需要按顺序合并,等价于只能合并相邻的两个点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];
}