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

真·正解:https://blog.csdn.net/ZscDst/article/details/80698624

Posted by 614984177 at 2018-06-15 16:02:07 on Problem 1015
本题和UVA - 323均可AC。
①可能是出自kuangbin大神的一种解法:由于路径的存储方式问题导致的BUG。 
某些情况下,关于dp[][]某种状态的最优解不唯一,上述做法会采取覆盖(或保留某一种答案)的方式,所以会有BUG,举个例子:dp[i][j] 状态下的最优解有两种:①1,2,3,4 ②1,5,6,7。假设我们保留了后面一种方案,而正确答案为  1,2,3,4,5,此时就无法得到的正确答案。 
该做法能AC数据较弱的POJ - 1015,但AC不了UVA - 323。 
②POJ1015-Jury Compromise 以及 uva 323正确二维DP解法,我的做法参考了该博主的做法,但是我感觉该博主的做法有个地方处理的不太好,就是j+subtraction[k],当subtraction[k]<0 时,会访问到负数位置。当subtraction[k]>0时,j+subtraction[k] 会访问到大于2∗fix的位置。 
但是该做法确实能AC,POJ - 1015 和 UVA - 323 两题。


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