Uoj#214.【UNR #1】合唱队形 题解
题意:
- 有$n$个小朋友要教唱歌,每个小朋友可能会学某一些音,每一秒发生的所有事件都是等概率的(包括已经发生的),事件即某个小朋友学(会)了某个音。问连续的一段长度为$m$的区间的小朋友会唱一段歌的期望事件。
- $1\le m\le n\le 30$
题解:
- 参考的大佬的博客地址
- 首先考虑一个问题:如果总共有$sum$,需要完成其中的$k$个课程的期望事件是:
- 长度为$m$的区间有$n−m+1$个,考虑枚举这些区间的完成情况,通过容斥计算贡献。
- 设$f_t$表示事件$t$之前任务没有完成的概率。
- 设$p_{S,t}$ 表示事件$t$之前区间集合$S$未被完成的概率。
- 则可以知道:
- 这个我们考虑复杂度,发现他是一个$O(2^{n−m+1}n^2)$的复杂度,似乎并不能怎么样。
- 但是当$n,m$较为接近时,这个算法还是比较靠谱的。
- 当$n−m$比较大时,我们考虑直接计算$F(k)$的贡献。
- 这个应该是可以$dp$的。设$dp[i][j][k]$表示考虑到第$i$个小朋友,到现在为止他需要学的音的集合是$j$,已经需要发生$k$个事件的贡献。那么最后只要将$\sum_{j}dp[n][j][k]$乘上$F(k)$加入答案即可。
- 初始状态$dp[0][0][0]=1$,转移方程分两种:
- $i$这个点开始的区间不在集合$S$中:
- $i$这个点开始的区间在集合$S$中(得是可以在):
- 这样的复杂度是 $O(2^mn^3)$ 的。
- 平衡两边复杂度后至少可以得到一个 $O(2^{\frac{n}{2}}n^3)$ 的做法,然后似乎就可以过了。
代码:
1 |
|