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

二维DP递推的存在性没有人证明过,无法严格证明子结构最优?

Posted by bxsj at 2016-04-23 08:07:54 on Problem 1015
最直观的三维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:
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