题意:给定一串数,问有多少种子串(非连续),他们相邻两个元素的差值小于等于d。

思路:d[i] 来表示以第i个数为结尾的方法数。那么我们在访问第i个元素的时候,就是去寻找之前 a[i]-d ~ a[i] + d之间的数即可。

这个地方需要用树状数组+离散化来优化。因为10w个数,离散到1~10w,然后求区间和的时候,先离散化,然后求和即可。

 

HDU 5550 Game Rooms(dp)

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

阅读全文

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

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

阅读全文

HDU 4261 Estimation(优先队列优化dp,区间中位数,区间减一个数的绝对值的和)

题意:给定一个序列A。现在让你在生成一个序列B,B的要求是恰好为k段相同的元素,且sigma|A[i]-B[i]|最小。 思路:我们要让一段序列减去一个相同的数的绝对值...

阅读全文

欢迎留言

*