HDOJ 5115 Dire Wolf

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5115

题目翻译

一行有(N)只狼,第(i)只狼有攻击力(A_{i})和攻击光环(B_{i})。当消灭一只狼的时候,主角会受到这只狼左右两只狼的攻击光环加成之后的这只狼的攻击力那么多的伤害,即(A_{i}+B_{i-1}+B_{i+1})。求如何使收到伤害最少然后消灭所有狼。

题解

区间DP。
DP[i][j]表示消灭区间i到j的狼所最少要受到的伤害。
转移的时候,我们就可以选择一匹狼,然后通过先消灭这匹狼左右的两个区间,再消灭这匹狼来转移到更大的区间。

代码