Snowdream

把總長(zhǎng)度求出來(lái)，然后用和背包問(wèn)題類似的dp算法求是否可以達(dá)到這個(gè)總長(zhǎng)度的一半，但是超時(shí)了。
找到一個(gè)優(yōu)化方案，結(jié)果0ms就過(guò)了，orz
http://162.105.81.202/course/problemSolving/dividingProve.doc
以下論證均轉(zhuǎn)自這篇文章。
 結(jié)論 對(duì)于任意一種珠寶的個(gè)數(shù)n，如果n>=8, 可以將n改寫(xiě)為 11（n為奇數(shù)） 或 12（n為偶數(shù)）。

證明：

對(duì)于任意一組數(shù)，6的個(gè)數(shù)為n(n>=8)

一、如果可以分成兩堆，我們可以分成兩種情況：
   1.
      兩堆里都有6，那么我們可知：把n改為n-2，仍然可分。
(兩堆各減一個(gè)6)
2. 只有一堆里有6，設(shè)為左邊，那么左邊的總和不小于6*8=48。
我們觀察，5*6=6*5 ，4*3=6*2 ， 3*2=6 ， 2*3=6 ， 1*6=6
而 5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45 < 48
由抽屜原理右邊必然存在
(多于5個(gè)的5 或者 多于2個(gè)的4 或者 多于1個(gè)的3
或者 多于2個(gè)的2 或者 多于5個(gè)的1)
即右邊至少存在一組數(shù)的和等于若干個(gè)6，比如右邊有3個(gè)4，這樣把左邊的2個(gè)6與右邊的3個(gè)4交換，則又出現(xiàn)左右都有6的情況。 根據(jù)1，我們還是可以把n改為n-2且可分的狀態(tài)不變。
綜合1，2。我們可以看出只要原來(lái)n的個(gè)數(shù)=8,我們就可以把它改為n-2，這樣操作一直進(jìn)行到n<8。我們可以得出結(jié)論，對(duì)于大于等于8的偶數(shù)，可以換成6。
對(duì)于大于8的奇數(shù)，可以換成7。換完之后仍然可分。

二、如果不能分成兩堆：
顯然改為n-2時(shí)同樣也不能分，那么對(duì)于大于等于8的偶數(shù)，可以換成6；對(duì)于大于8的奇數(shù)，可以換成7。換完之后仍然不可分。

綜合一、二，我們得出結(jié)論把不小于8的偶數(shù)改為8，大于8的奇數(shù)改為7，原來(lái)可分與否的性質(zhì)不會(huì)改變。

以上是對(duì)6的討論，同樣的方法可以推出
5的個(gè)數(shù) 6*4 + 4*4 + 3*4 + 2*4 + 1*4 = 64 < 5*13
即5的個(gè)數(shù)多于12時(shí)，偶數(shù)換為12，奇數(shù)換為11
4的個(gè)數(shù) 6*1 + 5*3 + 3*3 + 2*1 + 1*3 = 35 < 4*9
即4的個(gè)數(shù)多于8時(shí)，偶數(shù)換為8，奇數(shù)換為7
3的個(gè)數(shù) 5*2 + 4*2 + 2*2 + 1*2 = 24 < 3*9
即3的個(gè)數(shù)多于8時(shí)，偶數(shù)換為8，奇數(shù)換為7
2的個(gè)數(shù) 5*1 + 3*1 + 1*1 = 9 < 2*5
即2的個(gè)數(shù)多于4時(shí)，偶數(shù)換為4，奇數(shù)換為3
1的個(gè)數(shù) 多于5則必然可分(在總數(shù)是偶數(shù)的前提下)

綜上所述,
對(duì)于任意一種珠寶的個(gè)數(shù)n，如果n>=8, 可以將n改寫(xiě)為 11（n為奇數(shù)） 或 12（n為偶數(shù)）。

進(jìn)一步分析：
對(duì)每個(gè)數(shù)（1-6），以上只是粗略的估計(jì)，可以進(jìn)一步減少其最大有效取值，例如，
對(duì)于6，5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45
就有4和2不能同時(shí)出現(xiàn)，5和1不能同時(shí)出現(xiàn)，3個(gè)5和1個(gè)3不能同時(shí)出現(xiàn)，4個(gè)5不能和1個(gè)4同時(shí)出現(xiàn)等等，所以組合不出6的整數(shù)倍的情況的總價(jià)值至多為25，所以當(dāng)6的個(gè)數(shù)大于6時(shí)，奇數(shù)可改為5，偶數(shù)可改為6。
1-5 也有類似情況。

為了得出精確值，下面先我們討論這樣一個(gè)數(shù)論命題。

命題：
可重復(fù)的從自然數(shù)集中取出n個(gè)數(shù)（n>=2)，其中必有若干個(gè)數(shù)之和能被n整除。

證明：設(shè)取出的n個(gè)自然數(shù)為a1,a2,a3,.....an

考慮這樣的n+1個(gè)數(shù) 0, a1, a1+a2 , a1+a2+a3 , ...... , a1+a2+a3+...+an， 由于自然數(shù)模n的剩余類有n個(gè)，所以以上n+1個(gè)數(shù)中必有兩個(gè)同余。 這兩個(gè)數(shù)的差必被n整除，而且這兩個(gè)數(shù)的差就是原來(lái)的n個(gè)數(shù)中的一些數(shù)的和。
這就證明了命題。

由以上命題
對(duì)于6而言，我們至多從{1，2，3，4，5}中可重復(fù)的找出5個(gè)數(shù)使它們不能組合成6的倍數(shù)。
所以這些數(shù)的和小于等于5*5=25
對(duì)于5而言，我們至多從{1，2，3，4，6}中可重復(fù)的找出4個(gè)數(shù)使它們不能組合成5的倍數(shù)。
所以這些數(shù)的和小于等于6*4=24
對(duì)于4而言，我們至多從{1，2，3，5，6}中可重復(fù)的找出3個(gè)數(shù)使它們不能組合成4的倍數(shù)。
所以這些數(shù)的和小于等于3*6=18 ， 然而，兩個(gè)6就是4的倍數(shù)， 所以最多有一個(gè)6
此時(shí)不能有兩個(gè)5（2*5+6=16是4的倍數(shù)）， 最多才6 + 5 + 3 = 14 < 3*5 =15
所以這些數(shù)的和小于等于3*5=15
對(duì)于3而言，我們至多從{1，2，4，5，6}中可重復(fù)的找出2個(gè)數(shù)使它們不能組合成3的倍數(shù)。
所以這些數(shù)的和小于等于2*5=10

（6就是3的倍數(shù)，所以不能取6）

對(duì)于2而言，我們至多從{1，3，4，5，6}中可重復(fù)的找出1個(gè)數(shù)使它們不能組合成6的倍數(shù)。

所以這些數(shù)的和小于等于1*5=5



考慮到 4*6 < 25 < 5*6 , 我們可以算出6的最大有效個(gè)數(shù)為5 。

考慮到 4*5 < 24 < 5*5 , 我們可以算出5的最大有效個(gè)數(shù)為5 。但是其實(shí)應(yīng)該修正為6， 如果遇到如下特殊情況，左邊5個(gè)6，右邊6個(gè)5。此時(shí)雖然左右可以交換，但是交換后仍然只有一邊有5，與（一、2）中討論情況不符。

考慮到 3*4 < 15 < 4*4 , 我們可以算出5的最大有效個(gè)數(shù)為4 。但是其實(shí)應(yīng)該修正為5， 如果遇到如下特殊情況，左邊4個(gè)5，右邊5個(gè)4。此時(shí)雖然左右可以交換，但是交換后仍然只有一邊有4，與（一、2）中討論情況不符。

考慮到 3*3 < 10 < 4*3 , 我們可以算出5的最大有效個(gè)數(shù)為4 。但是其實(shí)應(yīng)該修正為5， 如果遇到如下特殊情況，左邊3個(gè)5，右邊5個(gè)3。此時(shí)雖然左右可以交換，但是交換后仍然只有一邊有3，與（一、2）中討論情況不符。

考慮到 2*2 < 5 < 3*2 , 我們可以算出5的最大有效個(gè)數(shù)為3 。 但是其實(shí)應(yīng)該修正為4，如果遇到如下特殊情況，左邊1個(gè)3和1個(gè)5，右邊4個(gè)2。此時(shí)雖然左右可以交換，但是交換后仍然只有一邊有2，與（一、2）中討論情況不符。


我們得出最后的精確結(jié)論：

奇數(shù)改為 偶數(shù)改為
6的個(gè)數(shù)大于5 5 4
5的個(gè)數(shù)大于6 5 6
4的個(gè)數(shù)大于5 5 4
3的個(gè)數(shù)大于5 5 4
2的個(gè)數(shù)大于4 3 4 



優(yōu)化后的代碼：