【BZOJ 4332】分零食

一种简单的思想是dp[i][j]表示前i个人,获得j个糖时所有情况的积的和,复杂度O(M^2)不可过


假如没有“所有没有糖的人都要在最后连续的一段”的限制,是一道倍增FFT的裸题


现在加入这个限制,没有关系,我们还是倍增FFT,用F[i][j],表示前i个人,获得j个糖,且每个人都有糖的时候所有情况的积的和,G[i][j]表示前i个人,至少有一个在最后的人没有获得糖的时候,所有情况的积的和。


倍增FFT进行转移,复杂度O(MlgMlgM)


代码:http://paste.ubuntu.com/15471029/


评论
热度(1)

© yjq_1999 | Powered by LOFTER