[BZOJ1037/Luogu2592][ZJOI2008]生日聚会Party(动态规划)

发布于 2018-05-08  180 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1037/Luogu2592][ZJOI2008]生日聚会Party(动态规划)

Description

今天是hidadz小朋友的生日,她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中,打算坐成一排玩游戏。为了游戏不至于无聊,就座的方案应满足如下条件:对于任意连续的一段,男孩与女孩的数目之差不超过k。很快,小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现,这样的就座方案其实是很多的,所以大家很快就找到了一种,那么到底有多少种呢?热爱数学的hidadz和她的朋友们开始思考这个问题…… 假设参加party的人中共有n个男孩与m个女孩,你是否能解答Susie和hidadz的疑问呢?由于这个数目可能很多,他们只想知道这个数目除以12345678的余数。

Tag

动态规划

解决思路

$$-$$
考虑如何限制这个任意连续段男女数目只差不超过$$k$$。
对于一个合法的序列,我们在这个序列右边加入一个人,那么是否能加入这个人取决于以原右端点为右边的所有序列中男-女的最大值和女-男的最大值。
所以设$$F[i][j][k][l]$$表示选择了$i$个男生,$j$个女生,右端点男-女的最大值为$k$,女-男的最大值为$l$时的方案数。按照当前选择放置男还是女来转移。
注意,由于可能出现男生永远比女生多或反过来的情况,所以$$k,l$$可能是负值,这个直接归到$0$的情况就好。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1037/Luogu2592][ZJOI2008]生日聚会Party(动态规划)


HNCJ OIer