首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

POJ 2096 Collecting Bugs:概率 DP 求期望天數

     編輯:關於C++

問題建模

n 類 Bug,s 個子系統。每天隨機發現一個 Bug,類別與子系統均勻獨立分布。求期望天數,使得「每類 Bug 至少出現一次」且「每子系統至少出現一次」。

狀態定義

dp[i][j]:已發現 i 類 Bug、j 個子系統有 Bug 時,達到目標 (n, s) 所需的期望剩餘天數。
邊界:dp[n][s] = 0。

轉移方程推導

當前狀態 (i, j),下一天四種情況:

情況概率新狀態
舊類、舊系統i/n * j/s(i, j)
新類、舊系統(n-i)/n * j/s(i+1, j)
舊類、新系統i/n * (s-j)/s(i, j+1)
新類、新系統(n-i)/n * (s-j)/s(i+1, j+1)

期望方程:
dp[i][j] = 1 + p00*dp[i][j] + p10*dp[i+1][j] + p01*dp[i][j+1] + p11*dp[i+1][j+1]
移項得:
dp[i][j] = (1 + p10*dp[i+1][j] + p01*dp[i][j+1] + p11*dp[i+1][j+1]) / (1 - p00)

計算順序

i 從 n 遞減到 0,j 從 s 遞減到 0(依賴右/下狀態)。

參考代碼(C++)

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved