討論串(共6篇) - [討論] GCJ結束了我要伸解法～ - 看板Prob_Solve

看板 [ Prob_Solve ]

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

共 6 篇文章

排序：最新先 | 最舊先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

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

推噓2(2推 )留言7則，0人參與作者Lucemia (生の直感、死の予感)時間17年前 (2008/07/30 21:42)資訊

內容預覽:

這題和 1a 一模一樣. 也可以看成是兩列元素要進行向量相乘求最小. 證明也一樣. 我猜應該也是dp, 還沒時間寫code實驗. state(i,j) 定為，第一項為i, 最後項為j的遞增數列數. 假設 j < i => state(i,j) = 0. 假設 i < j =>. sum( stat

(還有6個字)

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

推噓1(1推 )留言1則，0人參與作者Lucemia (生の直感、死の予感)時間17年前 (2008/07/29 20:36)資訊

內容預覽:

假設 vector1是 (a1,a2,... an),vector2 是 (b1, b2,... bn). n = 2時很好證:. n = k 時. 假設最大配最小解法不為最好,. 則存在一組向量為最好. 其中至少存在一組 i, j <= n. 滿足ai < aj, bi < bj. 此組向量內積為

(還有125個字)

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

推噓3(3推 )留言3則，0人參與作者yoco315 (眠月)時間17年前 (2008/07/29 19:57)資訊

內容預覽:

我可以問一下證明嗎. 雖然到處看到都是這個解答. 不過我不是很懂為什麼這樣 work. --. To iterate is human, to recurse is divine.. 遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch. --. ※ 發信站: 批踢踢實業坊(ptt.

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

推噓0(0推 )留言0則，0人參與作者yyc1217 (somo)時間17年前 (2008/07/29 18:57)資訊

內容預覽:

原文恕刪. 我認為這題並不是Greedy. 不過的確是最大配最小. 我的解法如下：. 1.將第一個向量的值由大排到小 O（nlgn）. 將第二個向量的值由小排到大 O（nlgn）. （一、二亦可顛倒）. 2.求兩個向量的scalar product，所得的數即為所求 O（n）. 即求X1Y1+X2Y

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

推噓1(1推 )留言2則，0人參與作者Lucemia (生の直感、死の予感)時間17年前 (2008/07/28 23:41)資訊

內容預覽:

就我知道的部份講一下. 這個解法也是我從其他人聽來的線索中拼湊出來的. 不確定是否就是最佳解. 1. 假設 3 + 5^.5 = X ==> X^2 = 6X -4. 由此可以導出遞迴關析式 X^n = 6X^(n-1) - 4X^(n-2). 但不能直接由此式算出X, X^2後跑迴圈去解. 因為

(還有584個字)

首頁

尾頁