http://acm.hdu.edu.cn/showproblem.php?pid=3625題意描述：有n個(gè)緊鎖的房間和這n個(gè)房間門上的n把鑰匙，每個(gè)房間中隨機(jī)鎖了一把鑰匙。你可以破壞一扇門，取出其中的鑰匙，嘗試用鑰匙打開另外的門（然后取出鑰匙去打開另外的門，或者接著破壞另外的門）。最多可以破壞k（<=n）扇門，但是第一扇門只能用鑰匙打開。求所有門能被打開（被破壞，或是被鑰匙打開）的概率。
傳說中的第一類斯特林?jǐn)?shù)。
如果用s[n][k]表示n個(gè)門中有k個(gè)環(huán)的情況數(shù)，則有：
s[n][k] = s[n - 1][k - 1] + (n - 1) * s[n - 1][k], 1 <= k <= n - 1
上面的公式可以這樣理解：當(dāng)前n - 1個(gè)門組成k - 1個(gè)環(huán)的時(shí)候，再加入第n個(gè)門形成一個(gè)單環(huán)即可；當(dāng)n - 1個(gè)門組成k個(gè)環(huán)時(shí)，要加入第n個(gè)門，為了不增加環(huán)的個(gè)數(shù)，只需要將n插在前n - 1個(gè)門的任意一個(gè)門之后即可。
初始化情況為：
s[i][0] = 0;
s[i][i] = 1, i >= 1
因?yàn)榈谝粋€(gè)門不能在環(huán)中，只需將第一個(gè)門在環(huán)中的情況減去，即是s[i][j] - s[i - 1][j - 1]才是合法的情況。
以下是代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 30
long long s[LEN][LEN];
int main()
{
int i, j;
int T;
int N, K;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &K);
memset(s, 0, sizeof(s));
for(i = 0; i <= N; i++)// init
s[i][i] = 1;
for(i = 1; i <= N; i++)
for(j = 1; j <= i; j++)
s[i][j] = (i - 1) * s[i - 1][j] + s[i - 1][j - 1];
long long sum = 0;
long long base = 0;
for(i = 0; i <= K; i++)
sum += s[N][i] - s[N - 1][i - 1];
for(i = 0; i <= N; i++)
base += s[N][i];
double rs = 1.0 * sum / base;
printf("%.4lf\n", rs);
}
//system("pause");
return 0;
}
posted on 2012-09-06 20:39
小鼠標(biāo) 閱讀(1196)
評論(0) 編輯 收藏 引用 所屬分類:
網(wǎng)選訓(xùn)練