bzoj2201 彩色圆环

bzoj2201 彩色圆环

​​ Description Input 仅有一行，该行给出依次两个正整数N, M，分别表示宝石的个数和宝石在变化时可能变成的颜色种类数。 Output 应仅有一行，该行给出一个实数E(R)，表示圆环的“美观程度”的期望值。 Sample Input 8 1 Sample Output

8.00000

【数据规模和约定】 100%的数据满足1 ≤ N ≤ 200, 1 ≤ M ≤ 10^9。 设dp[i][0/1]表示 我现在做了前i个并且以第1个为参照物的只 然后 第i个和第1个是否相同的期望（注意这个dp方程隐含了我 第一个和第二个不能存在相同的这个事实） 为了避免重复计算答案 统计答案的时候：我是假设我相同的长度是i 那么对答案做出的贡献就是i 然后同时还枚举了以他为第一个数所在连续长度为i的答案 进行转移的时候我需要分情况讨论 比如dp[i][0]=dp[j][0](枚举 前半段的长度 然后乘以贡献 概率（注意前后 都不相同 所以这时候的概率记得减去2 最后统计答案的时候 注意 计算答案时，枚举第1个数所在的连续段长度i，由于是环形，故包含第1个数的长度为i的连续段有i种放置方法，故ans+=i*i*f[n-i+1][0]*(1/m)^(i-1) 由于是环形 我们假设把前面枚举的那一段单独取出来 然后把他缩成一个点 然后再放回 这样原来的环就被我变成了一条链 统计答案的时候为什么只需要枚举这个长度的i种情况就好了 因为其他情况我在枚举其他长度的时候 直接被我算在期望的dp数组里了 这样才能保证不重不漏 比如编号1 2 3 4 5 6 7 然后我需要取长度为3 的 那么显然我可以是1 2 3 7 1 2, 6 7 1三种取法 那为什么不考虑转到下面的情况呢 因为当我枚举长度是4的时候会出现1 2 3 4的情况 那么我刚刚所说的转到下面的情况是不是被包含在5 6 7 这个dp的期望里了呢

#include#define N 220double p[N],dp[N][2];int n,m;int main(){ scanf("%d%d",&n,&m);dp[1][1]=1;p[0]=1; for (int i=1;i<=n;++i) p[i]=p[i-1]/m; for (int i=2;i<=n;++i){ for (int j=1;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。