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

思路:这种题得先发现问题的规律。

我们倒着思考这个问题,假设最终的队列的最后一位是初始队列的i。那么这个最终序列的结构一定是 (1~i-1的一个排列)+(i+1~n的一个排列) +  i

一定是这样的。试想,要是i最后一个进新队,那么他一定在栈的最底部等待,所以1~i-1一定以及进入新队列,然后i+1~n一定再次进入新队列,最后i进入。

这个顺序是固定的。

有了这一步之后,我们就可以轻松的区间dp了。

d[i][j][k] 表示原序列中的i~j所在的这一块的最右端的位置在k。然后转移一下就可以了。比较好写。

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

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

阅读全文

UVA 10688 – The Poor Giant (区间dp)

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

阅读全文

UValive 6938 Outer space invaders (区间dp+离散化)

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

阅读全文

欢迎留言

*