Re: [討論] GCJ結束了我要伸解法～
看板Prob_Solve (計算數學 Problem Solving)作者Lucemia (生の直感、死の予感)時間16年前 (2008/07/30 21:42)推噓2(2推 0噓 5→)留言7則, 4人參與討論串6/6 (看更多)
: 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
推
07/31 01:12, , 1F
07/31 01:12, 1F
→
08/01 00:44, , 2F
08/01 00:44, 2F
→
08/01 00:45, , 3F
08/01 00:45, 3F
推
08/01 19:19, , 4F
08/01 19:19, 4F
→
08/03 04:15, , 5F
08/03 04:15, 5F
→
08/03 04:18, , 6F
08/03 04:18, 6F
→
08/03 04:19, , 7F
08/03 04:19, 7F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 6 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
