题意:有n个饼干,分day天吃完,每天吃的饼干数量要小于m,问有多少种吃法可以把这n个饼干吃完。

思路:因为day为10^14,而n只有2000,所以我们如果把饼干全部吃完肯定大部分的天数都是吃0块饼干的。

那么我们只要把吃大于等于1块的天数找出来,把剩下0块的插进去即可。

d[i][j]来表示 i天吃j个饼干的方法数,对于第i天如果吃完n个饼干,那么总共有 d[i][n] 种方法。

对于每一种方法,我们可以放在day天里,总共是 d[i][n] * C(day, i) 种方法,day太大,需要lucas求一下。

在求解d[i][j]的时候,需要用树状数组维护一下前缀和。

 

HDU 5550 Game Rooms(dp)

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

阅读全文

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

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

阅读全文

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

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

阅读全文

欢迎留言

*