 /**//*
题意: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;
}
|