这道题是一道智力题
所以想了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