糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 1945 Power Hungry Cows 终极打表

这道题是一道智力题
所以想了n久,都想不出什么“数学方法”。甚至都想不出什么比较好的剪枝方法。
测了一下,普通的bfs比较慢。算到18步就开始就龟速了。
要算到21步才能得出1~20000的每一个答案。然而算到21步,在T8100 cpu的本本上都要跑半分钟,囧。。
所以没办法了,只能打表了。看了一下status。发现排在第一页的人打表的不少呢!哈哈。

但是问题来了。20000大小的数组,每个元素在1~21之间,如果这样表示出来
int arr = {1, 2, 3, ....}
那不得40k+左右吗。显然poj是不允许提交这么大的代码的!
但是status里面那些打表的人,代码都在20k~30k左右。这是怎么回事呢?
我有点怀疑别人看了答案,呵呵。但又不排除有方法能把代码长度控制好。
所以,考虑了下面几个方法:


1. 元素的范围是在 1~21 之间。所以要尽量用4bit表示一个元素。
统计了下,发现16以上的元素占了70%左右。所以规定:
>=16的元素,表示为 u4 arr[] = { (val&0xf) + 1 } 占用4bit
< 16的元素,表示为 u4 arr[] = { 0, val } 占用8bit
将它称之为"halfbyte"压缩
2. 霍夫曼压缩,lz77压缩
3. base64编码

这两天实在是闲的蛋疼。于是就把这个几个玩意写了一下。
经过测试,发现用 lz77 是获得的代码长度是最短的!仅9k!
统计如下:

=== generate: e:\test\1945_base64.cpp
base64 encode: 20032 -> 26712 133.35%
total: 20032 -> 26712 133.35%
file size: 27.22K

=== generate: e:\test\1945_halfbyte_base64.cpp
halfbyte encode: 20032 -> 11842 59.12%
base64 encode: 11842 -> 15792 133.36%
total: 20032 -> 15792 78.83%
file size: 17.15K

=== generate: e:\test\1945_halfbyte_huffman_base64.cpp
halfbyte encode: 20032 -> 11842 59.12%
huffman encode: 11842 -> 5964 50.36%
base64 encode: 5964 -> 7952 133.33%
total: 20032 -> 7952 39.70%
file size: 11.42K

=== generate: e:\test\1945_halfbyte_huffman_lz77_base64.cpp
halfbyte encode: 20032 -> 11842 59.12%
huffman encode: 11842 -> 5964 50.36%
lz77 encode: 5964 -> 8838 148.19%
base64 encode: 8838 -> 11784 133.33%
total: 20032 -> 11784 58.83%
file size: 15.78K

=== generate: e:\test\1945_huffman_base64.cpp
huffman encode: 20032 -> 6644 33.17%
base64 encode: 6644 -> 8860 133.35%
total: 20032 -> 8860 44.23%
file size: 11.71K

=== generate: e:\test\1945_huffman_lz77_base64.cpp
huffman encode: 20032 -> 6644 33.17%
lz77 encode: 6644 -> 8097 121.87%
base64 encode: 8097 -> 10796 133.33%
total: 20032 -> 10796 53.89%
file size: 14.21K

=== generate: e:\test\1945_lz77_base64.cpp
lz77 encode: 20032 -> 5422 27.07%
base64 encode: 5422 -> 7232 133.38%
total: 20032 -> 7232 36.10%
file size: 8.81K

所有方法都是0~32ms AC。
呵呵,代码太长了,就不贴了,给个下载:

/Files/varg-vikernes/1945.rar

posted on 2010-02-18 16:53 糯米 阅读(2622) 评论(2)  编辑 收藏 引用 所属分类: POJ

评论

# re: POJ 1945 Power Hungry Cows 终极打表[未登录]  回复  更多评论   

http://www.cppblog.com/varg-vikernes/archive/2010/02/18/108024.aspx
2014-07-30 16:07 | 糯米

# re: POJ 1945 Power Hungry Cows 终极打表[未登录]  回复  更多评论   

http://blog.csdn.net/lencle/article/details/7005546
2014-07-30 16:08 | 糯米

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理