来看下这个字符的编码的问题采用C语言怎么做了,位编码怎么得到的数字

Problem Description
  IP lookup is one of the key functions of routers for packets forwarding and classifying. Generally, IP lookup can be simplified as a Longest Prefix Matching (LPM) problem. That's to find the longest prefix in the Forwarding Information Base (FIB) that matches the input packet's destination address, and then output the corresponding Next Hop information.

  Trie-based solution is the most wildly used one to solve LPM. As shown in Fig.1(b), an uni-bit trie is just a binary tree. Processing LPM on it needs only traversing it from the root to some leaf, according to the input packet's destination address. The longest prefix along this traversing path is the matched one. In order to reduce the memory accesses for one lookup, we can compress some consecutively levels of the Uni-bit Trie into one level, transforming the Uni-bit Trie into a Multi-bit Trie.
  For example, suppose the strides array is {3, 2, 1, 1}, then we can transform the Uni-bit Trie shown in Fig.1(b) into a Multi-bit Trie as shown in Fig.1(c). During the transforming process, some prefixes must be expanded. Such as 11(P2), since the first stride is 3, it should be expanded to 110(P2) and 111(P2). But 110(P5) is already exist in the FIB, so we only store the longer one 110(P5).
  Multi-bit Trie can obviously reduce the tree level, but the problem is how to build a Multi-bit Trie with the minimal memory consumption (the number of memory units). As shown in Fig.1, the Uni-bit Trie has 23 nodes and consumes 46 memory units in total, while the Multi-bit Trie has 12 nodes and consumes 38 memory units in total.

Input
  The first line is an integer T, which is the number of testing cases.
  The first line of each case contains one integer L, which means the number of levels in the Uni-bit Trie.
  Following L lines indicate the nodes in each level of the Uni-bit Trie.
  Since only 64 bits of an IPv6 address is used for forwarding, a Uni-bit Trie has maximal 64 levels. Moreover, we suppose that the stride for each level of a Multi-bit Trie must be less than or equal to 20.

Output
  Output the minimal possible memory units consumed by the corresponding Multi-bit Trie.

Sample Input
1
7
1
2
4
4
5
4
3

Sample Output
38

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
数字到罗马字符的转换程序的实现的做法思路,采用C语言怎么做,都来看下
0
输入字符串进行一个编码的问题,采用C语言解决这个问题的技术的思路
0
给定的一个字符串,统计其中数字字符出现的次数,怎么采用C语言来回答这个问题的
0
字符串按照url地址的规则编码的问题,是怎么采用C语言的程序的格式的做法来正确地实现的
0
判断这个字符串是否是安全的,如何采用C语言的程序的设计的代码的形式来实现对于字符串安全的判断
3
C语言关于字符的问题?
1
这是一个关于C语言输出字符串长度的问题
1
这是一个关于C语言字符串初始化的问题和if语句问题
3
这是一个C语言的识别字符的程序
3
这是一个关于C语言字符的问题
1
C语言 关于获取最大字符串的问题
1
这是一个C语言判断字符个数程序的相关问题
2
这是一个关于C语言字符串的相关问题
1
求问简单的C语言字符串走马灯
2
C语言小白,想问一下关于字符串删除的问题怎么做?
1
刚刚学习c语言,做统计字符个数的时候遇到问题TAT,求大佬帮助~
1
用c语言怎么写字符串的反转?
2
高分悬赏,Java语言实现字符串的排序,怎么写这个程序,运用数组来实现,懂的人来回答
3
c语言输入字符串时输入指定的字符停止输入问题。
4
Java语言悬赏问题,Java语言输入一个字符串,统计字符串里面字母、数字、符号的个数分别是多少