Skip to content

14114: 【原4114】Kanna Code

题目

题目描述

author: 黄俊翔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4114 ## Description

大家都知道哈夫曼编码吧?对了,就是那个依据字母出现次数来构造符合前缀码规则(所有编码互不为前缀)的编码后文本总长度最短的编码方法。小林正在给公司的文本数据库编写一套哈夫曼编码(由于日文字符包括汉字,因此可以有数千个字母),以便于数据的压缩与传输。当她完成后给上司展示她的工作成果时,SB上司又双叒叕一次犯蠢,质问她为什么经过编码之后编码的字典序与原字母的字典序不同(废话,字母的字典序又不是按字频从多到少来排序的),让她回去重做,要求在经过编码之后,编码的字典序与原字母的字典序是相同的。

什么意思呢,举个例子吧。如果是5个字母(已按字典序排好),字频是3 1 4 2 5,那么哈夫曼编码应该是00 010 10 011 11。但显然,这个哈夫曼编码如果按照字典序来排序,和原来的顺序是不一样的。一个符合字典序的编码是000 001 010 011 100,但这套编码的文本编码后结果就未免太长了。

尽管是上司犯傻,小林还是决定开发一套全新的编码,并且命名为康娜编码(因为康娜的体长最短)。康娜编码就是在保证编码后字典序仍然不变的情况下,使文本总长度最短的编码方法(如果有多个编码可以使得文本的总长度最短,那就取编码本身字典序也最小的那个)。还是上面那个例子,它的康娜编码应当为000 001 01 10 11。尽管最终的文本长度比哈夫曼编码要长,但这已经是最优结果了。

尽管小林很想亲手写完康娜编码,但她终于因为爆肝过度而倒下,倒下前的最后一句话是希望你能够帮她完成这个任务。

Input Format

第一行一个整数\(T\),为数据组数。

接下来\(T\)组数据,每组数据两行。每组数据的第一行为一个正整数\(N\),代表字母的个数。接下来的一行包括\(N\)个非负整数,代表每个字母的字频(字母已按照字典序排序)。

Output Format

有\(T\)组输出,对应T组输入。

每组数据输出\(N\)行一个01字符串,代表对应字母的康娜编码。

Sample Input

2
5
3 1 4 2 5
7
3 1 4 100 5 6 7

Sample Output

000
001
01
10
11
0000
0001
001
01
100
101
11

Data Range

对于\(30\%\)的数据,\(N \le 8\)。

对于\(70\%\)的数据,\(N \le 200\)。

对于\(100\%\)的数据,\(1 \le T \le 5, 1 \le N \le 2000\),每个字母的字频小于\(10^9\)。

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4114.md
*/ 
#include <bits/stdc++.h>
#define INF 1000000000000000000ll
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[2005], jc[2005][2005] = {0};
ll f[2005][2005] = {0}, sum[2005] = {0};
char s[10005];
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read(), sum[i] = sum[i - 1] + a[i];
}
void dfs(int l, int r, int dep){
    if (l == r){
        s[dep] = '\0';
        printf("%s\n", s);
        return ;
    }
    s[dep] = '0';
    dfs(l, jc[l][r], dep + 1);
    s[dep] = '1';
    dfs(jc[l][r] + 1, r, dep + 1);
}
void solve(){
    for (int i = 1; i <= n; ++i)
        jc[i][i] = i;
    for (int l = 2; l <= n; ++l){
        for (int i = 1; i + l - 1 <= n; ++i){
            f[i][i + l - 1] = INF;
            for (int j = jc[i][i + l - 2]; j <= jc[i + 1][i + l - 1]; ++j){
                if (f[i][j] + f[j + 1][i + l - 1] + sum[i + l - 1] - sum[i - 1] < f[i][i + l - 1])
                    f[i][i + l - 1] = f[i][j] + f[j + 1][i + l - 1] + sum[i + l - 1] - sum[i - 1], 
                    jc[i][i + l - 1] = j;
            }
        }
    }
    dfs(1, n, 0);
}
int main(){
    int T = read();
    while (T--) {
        init();
        solve();
    }
    return 0;
}