作者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