HDU 5550 Game Rooms(dp)

11-09 1,234 views

题意:有n层楼,每层楼要建一个游泳池或者乒乓球馆,每层楼的人都有一些想去打乒乓球或者游泳的人,问怎么建立这些

体育设施,可以使得所有楼层的人去自己想去的地方的总距离最小,注意:n层楼中游泳池和乒乓球馆至少有一个。

思路:设计起来比较难的题目,就要观察这个题目的特点。我们把游泳池设为0,乒乓球设为1.

那么 这n层楼的特点一定是 …….1 1 1 0  1 1 0 1 1 0 0 0…… 抽象一下就是…..,一段1,一段0,一段1,一段0…..

一定是这样的。那我们就可以设计状态转移方程,d[i][1/0] 来表示 前i层楼,第i层楼一定是1,并且第i+1层一定是0的最小值。

转移也很简单,用get(1, j + 1, i) 来表示 [j + 1, i] 这些层楼里的状态是1的人到距离他最近的楼层的最小值是多少

d[i][0] = min(d[j][1] +get(1, j + 1, i))

d[i][1] = min(d[j][0] +get(0, j + 1, i))

好了。现在状态转移都搞定了,那么下一步怎么求 get函数呢?

其实也简单。[j + 1, i] 的人肯定有一些上楼,有一些下楼,假设现在数为 1 2 3 4 5 ,那么肯定是1 2下楼最近,4 5上楼最近,3上下都行,

所以直接把区间分一半,前一半下楼,下一半上楼。那么怎么快速求区间下楼的值呢?

其实写一写就可以发现,如果 [j + 1, i] 的人要到j这层楼去,那么就是[j+1, i]所有人到0层楼的距离 – 所有人从 j 到0的距离。所以求一下前缀和即可。

 

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

阅读全文

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

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

阅读全文

欢迎留言

*