這道題是一道智力題
所以想了n久，都想不出什么“數(shù)學(xué)方法”。甚至都想不出什么比較好的剪枝方法。
測(cè)了一下，普通的bfs比較慢。算到18步就開始就龜速了。
要算到21步才能得出1~20000的每一個(gè)答案。然而算到21步，在T8100 cpu的本本上都要跑半分鐘，囧。。
所以沒辦法了，只能打表了。看了一下status。發(fā)現(xiàn)排在第一頁的人打表的不少呢！哈哈。
但是問題來了。20000大小的數(shù)組，每個(gè)元素在1~21之間，如果這樣表示出來
int arr = {1, 2, 3, ....}
那不得40k+左右嗎。顯然poj是不允許提交這么大的代碼的！
但是status里面那些打表的人，代碼都在20k~30k左右。這是怎么回事呢？
我有點(diǎn)懷疑別人看了答案，呵呵。但又不排除有方法能把代碼長(zhǎng)度控制好。
所以，考慮了下面幾個(gè)方法：
1. 元素的范圍是在 1~21 之間。所以要盡量用4bit表示一個(gè)元素。
統(tǒng)計(jì)了下，發(fā)現(xiàn)16以上的元素占了70%左右。所以規(guī)定:
>=16的元素，表示為 u4 arr[] = { (val&0xf) + 1 } 占用4bit
< 16的元素，表示為 u4 arr[] = { 0, val } 占用8bit
將它稱之為"halfbyte"壓縮
2. 霍夫曼壓縮，lz77壓縮
3. base64編碼
這兩天實(shí)在是閑的蛋疼。于是就把這個(gè)幾個(gè)玩意寫了一下。
經(jīng)過測(cè)試，發(fā)現(xiàn)用 lz77 是獲得的代碼長(zhǎng)度是最短的！僅9k！
統(tǒng)計(jì)如下：
=== 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。
呵呵，代碼太長(zhǎng)了，就不貼了，給個(gè)下載：
/Files/varg-vikernes/1945.rar