本文主要是介绍[BalticOI 2009 Day1]甲虫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
甲虫
题解
很简单的一道dp题。
很容易看出是一道区间的dp题，但由于 m ≤ 1 0 6 m\leq 10^6 m≤106的数据范围限制，我们应该尽量避免让时间这一维出现在我们的dp中。
可它所有的水滴都会随着时间的发展而衰减，我们应该如何处理呢？
我们考虑一开始就将水滴加入状态中，之后再逐步递减。容易得到状态转移方程式
d p l , r , 0 = m a x ( d p l + 1 , r , 0 − ( n − r + l ) ( a l + 1 − a l ) , d p l + 1 , r , 1 − ( n − r + l ) ( a r − a l ) ) dp_{l,r,0}=max \left ( dp_{l+1,r,0}-(n-r+l)(a_{l+1}-a_{l}),dp_{l+1,r,1}-(n-r+l)(a_{r}-a_{l})\right ) dpl,r,0=max(dpl+1,r,0−(n−r+l)
这篇关于[BalticOI 2009 Day1]甲虫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
