题意:一排狼,每个狼都有一个伤害,还可以给周围的狼带来附加伤害,如果一个狼死了,就不会对相邻的狼有附加伤害,并且相邻的狼挨在一起。

问你杀死所有的狼所承受的最小伤害值。

思路:dp。。。矩阵链乘的变形,枚举最后一个杀死的狼,对于一个区间[i,j],如果最后一次杀死的是k, 那么k就会受到 b[i-1]和b[j+1]的伤害。一直这么递推下去即可。。 自己在想的时候,一直迷在先杀那只狼里无法自拔。。所以死的很是凄惨啊。。

 

 

HDU 4745 Two Rabbits(区间dp,最长环形回文串)

题意:给定一串环形数,两个兔子可以任选一个起点一个向左跳,一个向右跳,不可回头,两个兔子每次跳的位置数字要相同,并且 可以在同一个位置上,求最多可以...

阅读全文

HDU 4283 You Are the One (2012天津,区间dp)

题意:给定一个队列,有一个栈,你可以通过这个栈来获取一个新队列的顺序。比如队列最前面的元素可以先进栈,最后再入新的队,得到的序列的 sigma((i-1)*a[...

阅读全文

UVA 10688 – The Poor Giant (区间dp)

题意:重量越大的苹果越酸,越轻的越苦,中间的正好,一堆苹果中恰有一个苹果是甜的,找出这个苹果所需要的最小代价和。 思路:区间dp。 比较水,我们选了一...

阅读全文

欢迎留言

*