Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
尝试解释这个BUGIn 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator