「BZOJ2201」彩色圆环
Description
Input
仅有一行，该行给出依次两个正整数N, M，分别表示宝石的个数和宝石在变化时可能变成的颜色种类数。
Output
应仅有一行，该行给出一个实数E(R)，表示圆环的“美观程度”的期望值。
Sample Input
8 1
Sample Output
8.00000
「数据规模和约定」
100%的数据满足1 ≤ N ≤ 200, 1 ≤ M ≤ 10^9。
「数据规模和约定」
100%的数据满足1 ≤ N ≤ 200, 1 ≤ M ≤ 10^9。
题解
dp[i][j]表示前i个珠子，最后一个珠子和第一个是否相同(0,1)的期望值
这样可以 比较容易地 得到一个n^2的转移
p[i]表示i个珠子的颜色都相同的概率
至于统计答案
ans=p[n]*n表示环上只有一种颜色
for(int i=1;i<n;i++)ans+=i*i*f[n-i][0]*p[i]
这步是枚举第一珠子所在连续段长度，相当于n个位置里，有i个位置是第一珠子所在连续段，故长度i共有i种摆法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; double ans,p[205],f[205][2]; int main() { n=read();m=read(); p[1]=1; for(int i=2;i<=n;i++)p[i]=p[i-1]*1/m; f[0][1]=1; for(int i=0;i<=n;i++) for(int j=i+1;j<=n;j++) { f[j][0]+=(j-i)*p[j-i]*(f[i][0]*(m-2)/m+f[i][1]*(m-1)/m); f[j][1]+=(j-i)*p[j-i]*f[i][0]*1/m; } ans=p[n]*n; for(int i=1;i<n;i++) ans+=i*i*f[n-i][0]*p[i]; printf("%.5lf",ans); return 0; } |
Subscribe