/**//* 题意:n个人围成环,先选m个人,问有连续9个人被选上的概率 先考虑线性的,dp[i,j,k]表示前i个人中选j个,最后k个连续的方案数 有 dp[i,0,0]=1 dp[i,j,0] = ∑dp[i-1,j,k] dp[i,j,k]=dp[i-1,j-1,k-1]==dp[i-k,j-k,0] 而这里表明不用开3维,2维即可,最后1维可由dp[i-k,j-k,0]得到 则n个人选m个,不超过L个人连续的为 dp[n+1,m,0] k<=L
而对于环的,枚举断开处两端被连续选的个人i,j 保证连接处,其余处都没连续超过9即可 答案为 ∑dp[n-(i+1)-(j+1)+1][m-i-j][0] i+j<9 这里i+1,j+1表明需要一个空格来连接
*/ #include<cstdio>
double dp[1002][1002];
int main() { // dp[i,0,0]=1 // dp[i,j,0] = ∑dp[i-1,j,k] // dp[i,j,k]=dp[i-1,j-1,k-1]==dp[i-k,j-k,0] !!!!
//dp[0][0][0]=1; dp[0][0]=1; for(int i=1;i<=1001;i++) { for(int j=0;j<i;j++) { dp[i][j]=0; //dp[i][j][0]=0; for(int k=0;k<9&&k<=j;k++) { dp[i][j]+=dp[i-1-k][j-k]; //dp[i][j][0]+=dp[i-1][j][k]; //dp[i][j][k]=dp[i-k][j-k][0]; } } } int n,m; while(~scanf("%d%d",&n,&m)) { if(m<9||n<9){printf("%.6f%%\n",0.0);continue;} double sum = 0.0; for(int i=0;i<=m&&i<9;i++) for(int j=0;i+j<=m&&i+j<9&&(i+j+2)<=n;j++) sum+=dp[n-(i+1)-(j+1)+1][m-i-j]; if(m>n/2)m=n-m; double div=1.0; for(int i=1;i<=m;i++) div=div*(n-i+1)/i; printf("%.6f%%\n",100.0*(1-sum/div)); } return 0; }
|