Re: [討論] GCJ結束了我要伸解法～

[Lucemia (生の直感、死の予感)]

: 3a:greedy
: 最小的儘量全部塞一起。
: 目前還沒想到怎樣證orz...
: 時間複雜度：O(n lg n) (sorting)


這題和 1a 一模一樣

也可以看成是兩列元素要進行向量相乘 求最小
證明也一樣

: 3b:Divide and conquer and remember used stated (DP)
: 我們只在意餘數，所以其實在一個{1 .. 2*3*5*7}的ring就足以
: model我們看到的所有數字。
: State有strlen*2*3*5*7個，因為斷一次數字，後面要什麼數字，
: 只跟前面分別對2,3,5,7的餘數有關，跟真正加減起來的數字無關。
: 然後就對數字的每個數字之間都斷斷看，每次斷都加減看看就好。
: 時間複雜度： O(n) 因為2,3,5,7是constant.
: 3c.
: 不會....

我猜應該也是dp, 還沒時間寫code實驗

state(i,j) 定為，第一項為i, 最後項為j的遞增數列數

假設 j < i => state(i,j) = 0
假設 i < j =>

        sum( state(i,k) * state(k,j) | 對於所有 k 介於i,j間 且滿足 i<k<j)


所有可能數則為 sum(state(i,j) for all i,j)

大概是這樣 也可能有問題

煩請指正了。


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.88.50
推 ledia:最後這題意思是 O(n^3) 嗎?
→ Lucemia:實際做了發現 這題很明顯不是要考dp的, N太大了
→ Lucemia:從後面開始算 累計排列組合數就好
推 Arton0306:這一題要O(NlogN)大測資才會過
→ scan33scan33:用segment tree建dp的內表?
→ Lucemia:對 要透過 segment tree 來記
→ Lucemia:GCJ Group 上有人提供 bit indexed tree 的解法 很漂亮