有 \(n\) 种元素，给出每个元素的出现次数 \(a_i\) ，求一种 \(01\) 编码方案使得满足以下条件：

1. 没有一个编码是另一个的前缀
2. 最小化编码后文本的总长
3. 编码后按字典序保持原来的顺序

输出编码方案

\(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)\)

代码

#include 
    
     using 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;}