2013年6月18日 星期二

一道神祕題

給你兩個數字,A, B(A, B <= 10000)

你可以把他們各自拆成乘積:

33 -> 3, 11
24 -> 2, 3, 4
18 -> 2, 9

拆完的數字,由小排到大,計算差的平方和

EX:

33 40

-> 3, 11, 5, 8 -> 3, 5, 8, 11 -> (3-5)^2+(5-8)^2+(8-11)^2

= 22

而剛好這也就是所有拆法的「差的平方和」的最小值

給兩數字,求「差的平方和」的最小值

===========================

這種,近乎nHm的怪異題型,碰到就要先試試看DP

以某個數字X結尾的序列,A還剩A'沒拆,B還剩B'沒拆

最少的cost 為 DP[X][A'][B'],這樣。

可知A'會是A的因數,B'也是,X則是其一的因數

在1 ~ 10000裡,因數最多的數字也只有64個

所以DP的空間複雜度是64^3

至於要怎麼轉移,其實就看倒數第二是誰就行了

全部的複雜度是64^4。

但是,問題是他會問1000次:

1000 * 64^4 = 16777216000 = 10^10,就GG了




那要怎麼辦呢?

其實只要壓掉一個64就可以了

不是什麼性質,也沒有什麼怪東西

這裡不要想太多,簡單的DP優化而已 :)

http://ideone.com/hCStyp