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 |
二维DP递推的存在性没有人证明过,无法严格证明子结构最优?最直观的三维DP状态是: int f[200][21][840];f(i,j,k)前i个人里选j个候选人,总辩控差绝对值为k的时候,辩控总和最大值为f(i,j,k),状态转移很清晰,规模是N*M*K,是一个三维循环。 有疑问的二维DP状态是 int f[21][840];f(i,j)存放i个候选人,总辩控差绝对值为j,辩控总和为f(i,j) 这个状态转移的核心递推逻辑是,如果选i个候选人时的总辩控差在j,那么挨个剔除一个人,总共有i种剔除法,一定有一种剔除法,使得剩下的i-1个人,记它的总辩控差为k,是满足总辩控和等于f(i-1,k)的,也就是说存在剔一个人后正好是辩控和最大的子问题最优解。 但是试想一下,如果i个候选人中剔除的是第p个人,剩下的i-1个人的辩控差是k,如果满足f(i-1,k)的选人方式正好包含了第p个人呢?那这时候这种状态转移的逻辑是不成立的。除非我们能严格证明,i个候选人中剔除p个人有i种剔除法,至少有一种剔法是不会出现f(i-1,k)的选人集合不包含剔除的那个人,但是好像并没有办法给出严格证明,为什么至少存在一种剔法满足递推过程。 求高手解惑,困扰了很久了。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator