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