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 |
真·正解:https://blog.csdn.net/ZscDst/article/details/80698624本题和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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator