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 |
Re:请教这道题怎么dp?In Reply To:Re:请教这道题怎么dp? Posted by:o_oXo_o at 2006-07-29 16:31:42 > 对于整个牌的序列,最左端和最右端的牌是不能被取走的,除这两张以外的所有牌 > ,必然有一张最后取走。取走这最后一张牌有一个仅与它本身以及最左端和最右端的 > 牌的值有关的得分,这个分值与其他牌没有任何关系。当这张最后被取走的牌被定 > 下来以后(假设位置为j), 最左端到j之间的所有牌被取走时所造成的得分必然只与 > 这之间的牌有关从而与j到最右端之间的牌独立开来。这样就构成了两个独立的子 > 区间,出现重叠子问题。于是问题的解就是 > 取走最后一张牌的得分+两个子区间上的最小得分 > 不妨假设当前区间为[b, e],在(b,e)之间枚举最后一张被取走的牌,通过最优子问题 > 求出当前区间的最优解: > opt[b][e] = min{ opt[b][j]+opt[j][e] + val(b,j,e); }; > b+1<= j <=e-1 > val(b,j,e)是取走j所造成的得分,即第b,j,e这三张牌的积。 > 空间o(n^2), 时间o(n^3) Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator