CCF 压缩编码

一、试题

问题描述
　　给定一段文字，已知单词a1, a2, …, an出现的频率分别t1, t2, …, tn。可以用01串给这些单词编码，即将每个单词与一个01串对应，使得任何一个单词的编码（对应的01串）不是另一个单词编码的前缀，这种编码称为前缀码。
　　使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。一段文字经过前缀编码后的长度为：
　　L=a1的编码长度×t1+a2的编码长度×t2+…+ an的编码长度×tn。
　　定义一个前缀编码为字典序编码，指对于1 ≤ i < n，ai的编码（对应的01串）的字典序在ai+1编码之前，即a1, a2, …, an的编码是按字典序升序排列的。
　　例如，文字E A E C D E B C C E C B D B E中， 5个单词A、B、C、D、E出现的频率分别为1, 3, 4, 2, 5，则一种可行的编码方案是A:000, B:001, C:01, D:10, E:11，对应的编码后的01串为1100011011011001010111010011000111，对应的长度L为3×1+3×3+2×4+2×2+2×5=34。
　　在这个例子中，如果使用哈夫曼(Huffman)编码，对应的编码方案是A:000, B:01, C:10, D:001, E:11，虽然最终文字编码后的总长度只有33，但是这个编码不满足字典序编码的性质，比如C的编码的字典序不在D的编码之前。
　　在这个例子中，有些人可能会想的另一个字典序编码是A:000, B:001, C:010, D:011, E:1，编码后的文字长度为35。
　　请找出一个字典序编码，使得文字经过编码后的长度L最小。在输出时，你只需要输出最小的长度L，而不需要输出具体的方案。在上面的例子中，最小的长度L为34。
输入格式
　　输入的第一行包含一个整数n，表示单词的数量。
　　第二行包含n个整数，用空格分隔，分别表示a1, a2, …, an出现的频率，即t1, t2, …, tn。请注意a1, a2, …, an具体是什么单词并不影响本题的解，所以没有输入a1, a2, …, an。
输出格式
　　输出一个整数，表示文字经过编码后的长度L的最小值。
样例输入
5
1 3 4 2 5
样例输出
34
样例说明
　　这个样例就是问题描述中的例子。如果你得到了35，说明你算得有问题，请自行检查自己的算法而不要怀疑是样例输出写错了。
评测用例规模与约定
　　对于30%的评测用例，1 ≤ n ≤ 10，1 ≤ ti ≤ 20；
　　对于60%的评测用例，1 ≤ n ≤ 100，1 ≤ ti ≤ 100；
　　对于100%的评测用例，1 ≤ n ≤ 1000，1 ≤ ti ≤ 10000。

二、代码

拿到题目看前缀编码，首先想到的肯定是赫尔曼树（最优二叉树），但是题目中要求按字典序。由于按字典序我们二叉树的叶子节点需要刚好按照输入的节点顺序排列，不能改动，所以就强行按照输入的节点顺序生成二叉树，最后得到结果35（错误）。错误代码如下：

#include<cstdio>
#include<vector>

using namespace std;

int main(){
    int n;
    vector<int> t;
    int cost = 0;
    int minw;
    vector<int>::iterator left;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        int cint;
        scanf("%d", &cint);
        t.push_back(cint);
        cost += cint;
    }

    while(t.size()!= 1){
        for(vector<int>::iterator it = t.begin(); it!= t.end()-1; it++){
            if(it==t.begin()){
                minw = *it+ *(it+1);
                left = it;
            }
            int a = *it + *(it+1);
            if( *it + *(it+1) < minw ){
                minw = *it+ *(it+1);
                left = it;
            }
        }
        *left = minw;
        cost += minw;
        t.erase(left+1);
    }

    if(n==1){
        printf("%d", t[0]);
    }else{
        printf("%d", cost-t[0]);
    }

    return 0;
}

那么为啥不能呢？原因在于赫尔曼树每次要求取得是两个最小权值的树组成二叉树，这两个最小权值在所有权值排列中没有位置限制。而由于本题要求只能按字典序，一开始叶子节点的位置就已经排列好了，这也就是要求我们只能取相邻两个最小权值的组成二叉树。所以形成上面错误代码。那么就是说单纯使用赫尔曼树不行。但是其给我们一个思路，从底往上建树。由于叶子节点已经排列好，那么我们可以使用动态规划建树。建树过程如下表（为啥使用表，因为其key值刚好可以对应我们状态方程的key）：

上表中，斜对线的1，3，4，2，5是输入的叶子节点权值，然后首先计算相邻两个叶子节点组成树的长度分别为4，7，6，7。然后考虑3个相邻叶子节点组成长度为，以1，3，4节点为例，可以用1和（3，4）组合和（1，3）和4组合两种方式，选取最小长度，如此反复就能算出最终答案。转换成二叉树形式就是：

上图就是生成的最优结果，每个节点内值表示底下几个叶子节点的组合生成的最小长度。从中我们可以看出每一个节点的最小长度是它的左右子节点最小长度和加上所有叶子节点权值。可以理解为左右子节点已经把其各自的叶子结点的长度计算好，现在要把左右子节点组合成一个新的树，那么对于其底下的叶子结点而言都只是在原有基础上增加一倍权值。所以动态规划的最小长度状态方程为：
tree[i][j] = tree[i][k] + tree[k+1][j] + w[j] - w[i-1] （i<=k<=j）。其中w[j]表示前j个数组成的权值和。
最终代码：

#include<cstdio>

using namespace std;

// 注意后面由于直接用到某些数值，且初始赋值tree[i][i]为0，所以声明了全局变量。如果是局部变量在使用前需要先赋值。
int w[1050];
int tree[1050][1050];

int main(){
    int n;
    int t[1050];

    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &t[i]);
        w[i] = w[i-1] + t[i];
    }

    // 遍历方格一半（除去对角线），则外层需要遍历n-1次。
    for(int j=2; j<=n; j++){
        // 沿斜对角线遍历，[1][2],[2][3],[3][4],[4][5],[1][3],[2][4],[3][5]...例如[3][5]刚好对应于将将第三到第五数字进行建树的最小长度。
        for(int row=1,col=j; row<=n-j+1; row++,col++){
            // 对当前要计算的小长度首先赋值为最大值。
            tree[row][col] = 1<<30;
            // 循环遍历检测选择哪两颗子树形成的长度最小。
            for(int k=row; k<col; k++){
                int temCost = tree[row][k] + tree[k+1][col] + w[col] - w[row-1];
                if(temCost<tree[row][col]){
                    tree[row][col] = temCost;
                }
            }
            printf("%d%s", tree[row][col],"\n");
        }
    }

    printf("%d", tree[1][n]);
    return 0;
}