有 \(n\) 种元素,给出每个元素的出现次数 \(a_i\) ,求一种 \(01\) 编码方案使得满足以下条件:
- 没有一个编码是另一个的前缀
- 最小化编码后文本的总长
- 编码后按字典序保持原来的顺序
输出编码方案
\(n\leq2000\)
dp,四边形不等式
可以发现若只有前两个限制就是求哈夫曼编码(但这和本题并没有什么关系
令 \(s_i=\displaystyle\sum_{k=1}^ia_i\) , \(f_{i,\ j}\) 表示将区间 \([l,\ r]\) 的元素的编码建树后的最小权重和
则 \(f_{i,\ j}=\displaystyle\min_{i\leq k<j}\{f_{i,\ k}+f_{k+1,\ j}+s_j-s_{i-1}\}\) ,即将 \([i,\ k]\) 补上 \(0\) ,将 \([k+1,\ j]\) 补上 \(1\) ,这满足字典序递增
可以发现这满足四边形不等式,于是可以优化到 \(O(n^2)\)
时间复杂度 \(O(n^2)\)
代码
#includeusing namespace std;typedef long long ll;const int maxn = 2010;string s;int n, pos[maxn][maxn];ll sum[maxn], f[maxn][maxn];void print(int l, int r) { if (l == r) { cout << s << endl; return; } s += '0', print(l, pos[l][r]), s.pop_back(); s += '1', print(pos[l][r] + 1, r), s.pop_back();}int main() { freopen("codes.in", "r", stdin); freopen("codes.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%I64d", sum + i); pos[i][i] = i, sum[i] += sum[i - 1]; } for (int i = 2; i <= n; i++) { for (int j = 1; i + j - 1 <= n; j++) { int l = j, r = i + j - 1; for (int k = pos[l][r - 1]; k <= pos[l + 1][r]; k++) { if (!pos[l][r] || f[l][k] + f[k + 1][r] < f[l][r]) { f[l][r] = f[l][k] + f[k + 1][r], pos[l][r] = k; } } f[l][r] += sum[r] - sum[l - 1]; } } print(1, n); fclose(stdin), fclose(stdout); return 0;}