ZOJ 2561 Order-Preserving Codes
Order-Preserving Codes
64-bit integer IO format: %lld Java class name: Main
Binary code is a mapping of characters of some alphabet to the set of finite length bit sequences. For example, standard ASCII code is a fixed length code, where each character is encoded using 8 bits.
Variable length codes are often used to compress texts taking into account the frequencies of occurence of different characters. Characters that occur more often get shorter codes, while characters occuring less often -- longer ones.
To ensure unique decoding of variable length codes so called prefix codes are usually used. In a prefix code no code sequence is a proper prefix of another sequence. Prefix code can be easily decoded scanning the encoded sequence from left to right, since no code is the prefix of another, one always knows where the code for the current character ends and the new character starts.
Among prefix codes, the optimal code is known, so called Huffman code. It provides the shortest possible length of the text among all prefix codes that separatly encode each character with an integer number of bits.
However, as many other codes, Huffman code does not preserve character order. That is, Huffman codes for lexicographically ordered characters are not necessarily lexicographicaly ordered.
In this problem you are asked to develop a prefix code that would be optimal for the given text among all order-preserving prefix codes. Code is called order-preserving if for any two characters the code sequence for the character that goes earlier in the alphabet is lexicographically smaller.
Since text itself is not essential for finding the code, only the number of occurences of each character is important, only this data is given.
Input:
The input consists of several test cases
For each test case, the first line contains n -- the number of characters in the alphabet (2 <= n <= 2000). The next line contains n integer numbers -- the number of occurences of the characters in the text for which the code must be developed (numbers are positive and do not exceed 109). Characters are described in the alphabetical order.
Output:
For each test case, Output n bit sequences, one on a line -- the optimal order-preserving prefix code for the described text.
Sample Input:5 1 8 2 3 1Sample Output:
00 01 10 110 111
Source
Author
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL INF = 0x3f3f3f3f3f3f3f3f; 5 const int maxn = 2005; 6 LL dp[maxn][maxn],sum[maxn]; 7 int s[maxn][maxn],n; 8 void dfs(int x,int L,int R) { 9 if(L >= R) { 10 putchar('\n'); 11 return; 12 } 13 if(x <= s[L][R]) { 14 putchar('0'); 15 dfs(x,L,s[L][R]); 16 } else { 17 putchar('1'); 18 dfs(x,s[L][R] + 1,R); 19 } 20 } 21 int main() { 22 while(~scanf("%d",&n)) { 23 for(int i = 1; i <= n; ++i) { 24 scanf("%lld",sum + i); 25 s[i][i] = i; 26 sum[i] += sum[i-1]; 27 } 28 for(int i = 2; i <= n; ++i) { 29 for(int j = 1; j + i - 1 <= n; ++j) { 30 int k = j + i - 1; 31 dp[j][k] = INF; 32 for(int t = s[j][k-1]; t <= s[j+1][k]; ++t) { 33 LL tmp = dp[j][t] + dp[t+1][k] + sum[k] - sum[j-1]; 34 if(dp[j][k] > tmp) { 35 dp[j][k] = tmp; 36 s[j][k] = t; 37 } 38 } 39 } 40 } 41 for(int i = 1; i <= n; ++i) dfs(i,1,n); 42 } 43 return 0; 44 }
相关文章
- Linq-排序Order By
- Leetcode: Binary Tree Vertical Order Traversal
- System.Xml.XmlException: There is no Unicode byte order mark. Cannot switch to Unicode.
- sql server 中关于Order By 在子查询嵌套中的出错的解决方法!
- SQL预编译中order by后为什么不能参数化原因
- Oracle-除了会排序,你对ORDER BY的用法可能一无所知!
- mysql-order by 多个字段排序实现组内排序
- 【LeetCode】103. Binary Tree Zigzag Level Order Traversal
- order by与索引(转载)
- [LeetCode] 987. Vertical Order Traversal of a Binary Tree 竖直遍历二叉树
- [LeetCode] N-ary Tree Level Order Traversal N叉树层序遍历
- 【bzoj1391】[Ceoi2008]order 网络流最小割
- [Mysql] ORDER BY排序检索数据