题意:对于一个序列,从第一个数开始,要么把一个数放在上面,要么放在下面,要么不放,使得数字从上到下递增(非严格),求最多的数字个数。

最初做这个题。 构造了好几种状态都不行。

后来想了想 其实就是对于某一个位置。就是求他后面包括自身在内的最大递增序列和最大递减序列的个数和就好了。但是非严格递增递减。

如果序列是 3 3 3, 对于第一个位置,递增长度为3,递减长度为3.那么总长会算为  6. 所以对于递增/递减 要分为 严格递增/ 严格递减/非严格递增/非严格递减。

结果要组合一下。 一个严格一个非严格这样组合取最大值。

 

HDU 5550 Game Rooms(dp)

题意:有n层楼,每层楼要建一个游泳池或者乒乓球馆,每层楼的人都有一些想去打乒乓球或者游泳的人,问怎么建立这些 体育设施,可以使得所有楼层的人去自己想...

阅读全文

Aizu 2595 Cookie Counter(dp+Lucas定理+树状数组优化)

题意:有n个饼干,分day天吃完,每天吃的饼干数量要小于m,问有多少种吃法可以把这n个饼干吃完。 思路:因为day为10^14,而n只有2000,所以我们如果把饼干全...

阅读全文

HDU 3450 Counting Sequences(dp+离散化+树状数组)

题意:给定一串数,问有多少种子串(非连续),他们相邻两个元素的差值小于等于d。 思路:d[i] 来表示以第i个数为结尾的方法数。那么我们在访问第i个元素的时...

阅读全文

2 条评论

欢迎留言

*