题意:给定一个序列A。现在让你在生成一个序列B,B的要求是恰好为k段相同的元素,且sigma|A[i]-B[i]|最小。

思路:我们要让一段序列减去一个相同的数的绝对值的和最小,试试就会发现,用的是中位数。

那这个中位数怎么求呢?思路很巧妙,用的是两个优先队列(大顶堆和小顶堆)动态维护,保证其中一个队列里面的值大于另外一个队列,并且个数相同,那么小顶堆的top就是中位数。

那么dp状态转移也比较简单 d[i][j] 表示前i个数分成j段的最小值。

那么现在就是怎么最快的求出一段区间的sigma值最小呢? 我自己觉得很机智的写了一个 pre[i][j] 来表示前i个数同时减去j的绝对值的和,维护一个前缀和即可。结果提交上去给我卡了MLE。

看了网上题解之后,发现。。。太巧妙了。。

在我们求中位数的时候,维护的两个堆。假设小顶堆为5,6.大顶堆为2, 4. 那么中位数为mid。得到的结果为5 – mid + mid – 2 + 6 – mid + mid – 4=5 + 6 – 2 – 4

恰好就是两个堆的差值。。奇数的情况特殊处理一下即可。。 太神奇了。。然后就可以边动态求中位数的边更新差值了。。。

 

 

 

 

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个元素的时...

阅读全文

欢迎留言

*