作者Lucemia (生の直感、死の予感)
看板Prob_Solve
標題Re: [討論] GCJ結束了我要伸解法～
時間Tue Jul 29 20:36:32 2008
※ 引述《yoco315 (眠月)》之銘言：
: ※ 引述《yyc1217 (somo)》之銘言：
: : 不過的確是最大配最小
: 我可以問一下證明嗎
: 雖然到處看到都是這個解答
: 不過我不是很懂為什麼這樣 work
假設 vector1是 (a1,a2,... an),vector2 是 (b1, b2,... bn)
n = 2時很好證:
n = k 時
假設最大配最小解法不為最好,
則存在一組向量為最好
其中至少存在一組 i, j <= n
滿足ai < aj, bi < bj
此組向量內積為
S = a1 * b1 + a2 * b2 + ...ak * bk
= sum(ak | k 不等於 i, j) + ai * bi + aj * bj
> sum(ak | k 不等於 i, j) + ai * bj + aj * bi
(由n = 2時得到結果 )
與假設相抵
故可以歸繆得證
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.88.50
※ 編輯: Lucemia 來自: 140.113.88.50 (07/29 20:39)
1F：推 scan33scan33:謝謝！y 08/03 03:46