题意:有n个机器人,每个机器人在 ai 时间出现,在 bi 时间消失,它所在的位置有一个高度 hi,发射一个武器可以消灭高度为h的所有机器人,花费h,问消               灭所有的机器人,需要的最大的花费。

思路:

1.最多300个机器人,也就是最多有600个时间点,离散化为 1~600到这个时间上。

2.然后区间dp,d[i][j] 来表示 在时间i~j这个时间内,把所有机器人都消灭的最小花费。(不包括i,j这个时间点)

3.状态转移有点分治的感觉,把在i~j范围内的机器人全消灭,肯定需要的攻击力为最大的h,然后在这个区间内的任意一点攻击,都可以消灭这个,

那么就是min(d[i][j], d[i][k] + h + d[k][j])。跨过k点的一定不和 i~k,k~j重复。

 

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

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

阅读全文

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

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

阅读全文

UVA 10688 – The Poor Giant (区间dp)

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

阅读全文

欢迎留言

*