Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

尝试解释这个BUG

Posted by haqishen at 2015-02-07 13:03:16 on Problem 1015 and last updated at 2015-02-07 13:06:34
In Reply To:对标准算法提出的怀疑 Posted by:CZDleaf at 2011-07-22 09:52:21
创建数组dpsub[m][n],m是需要挑选的人数,n是总人数
用dpsub[i][j]表示:当挑选第i个juror时,选择了第j个candidate,此时最优的|sum(D)-sum(P)|.
为了避免同一个人的重复出现,计算dpsub[i][j]的值之前,我们需要查询之前第j个candidate是否已经出现过。
所以我们要用path[i][j]来记录当挑选第i个juror时,选择了第j个candidate时,上次选择的第i-1号juror的编号。
于是这样path数组就记录下了所有子问题的最优路径。
于是问题就来了,子问题的最优路径在极少数情况下并不唯一。
假如现在有两条路径1,2,3,4和1,5,6,7。这两条路径的dp值相同。
我们开始选择第5个人,假设选择8号当做第五人时,搜索到的最优子恰好是1,2,3,4这条路径(第二条路径的值与该路径完全一样,所以第二条路径的信息就被忽略了!)
所以到了第五个人,我们的最优解路径只剩下一条:1,2,3,4,8。
我想说到这里大家应该就已经明白了,假如正确答案的路径是156789,由于我们中途抛弃了1567路径,我们就再也得不出正确答案了!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator