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

可以在同一个位置上,求最多可以跳多少次。

思路:放了一个环上,如果从起点反向之后,每次跳的位置的数字相同,我们把他们的相遇位置切开,可以发现是一个回文串。

所以问题就是一个环求最长的回文串了。按照平常的思路,倍增这个串,然后正常求就可以了。

有一个问题就是对于偶数长度的时候,如第二组样例,我们可以把他看成n-1的串,最终跳到了1上。

 

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

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

阅读全文

UVA 10688 – The Poor Giant (区间dp)

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

阅读全文

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

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

阅读全文

欢迎留言

*