作者Lucemia (生の直感、死の予感)
看板Prob_Solve
標題Re: [討論] GCJ結束了我要伸解法～
時間Wed Jul 30 21:42:39 2008
: 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
1F：推 ledia:最後這題意思是 O(n^3) 嗎? 07/31 01:12
2F：→ Lucemia:實際做了發現 這題很明顯不是要考dp的, N太大了 08/01 00:44
3F：→ Lucemia:從後面開始算 累計排列組合數就好 08/01 00:45
4F：推 Arton0306:這一題要O(NlogN)大測資才會過 08/01 19:19
5F：→ scan33scan33:用segment tree建dp的內表? 08/03 04:15
6F：→ Lucemia:對 要透過 segment tree 來記 08/03 04:18
7F：→ Lucemia:GCJ Group 上有人提供 bit indexed tree 的解法 很漂亮 08/03 04:19