程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu3625--Examining the Rooms

hdu3625--Examining the Rooms

編輯:C++入門知識

題意描述:有n個緊鎖的房間和這n個房間門上的n把鑰匙,每個房間中隨機鎖了一把鑰匙。你可以破壞一扇門,取出其中的鑰匙,嘗試用鑰匙打開另外的門(然後取出鑰匙去打開另外的門,或者接著破壞另外的門)。最多可以破壞k(<=n)扇門,但是第一扇門只能用鑰匙打開。求所有門能被打開(被破壞,或是被鑰匙打開)的概率。
傳說中的第一類斯特林數。
如果用s[n][k]表示n個門中有k個環的情況數,則有:
s[n][k] = s[n - 1][k - 1] + (n - 1) * s[n - 1][k], 1 <= k <= n - 1
上面的公式可以這樣理解:當前n - 1個門組成k - 1個環的時候,再加入第n個門形成一個單環即可;當n - 1個門組成k個環時,要加入第n個門,為了不增加環的個數,只需要將n插在前n - 1個門的任意一個門之後即可。
初始化情況為:
s[i][0] = 0;
s[i][i] = 1, i >= 1
因為第一個門不能在環中,只需將第一個門在環中的情況減去,即是s[i][j] - s[i - 1][j - 1]才是合法的情況。
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved