AOJ - SNAIL

dp[i][j]=dp[i][j]= ii 번째 날이고 jj 만큼 올라왔을 때 mm 일까지 갔을 때 nn 이상일 확률

이라고 할 때,

dp[i][j]=0.75⋅dp[i+1][j+2]+0.25⋅dp[i+1][j+1]dp[i][j]=0.75 \cdot dp[i+1][j+2] + 0.25 \cdot dp[i+1][j+1] 이 된다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vector<vector<double>> dp(m + 1, vector<double>(n * 2 + 1, -1));  
   function<double(int, int)> fn = [&](int i, int j) -> double {  
      if (j >= n) return 1;  
      if (i == m) return 0;  
      double &ret = dp[i][j];  
      if (ret > -0.5) return ret;  
  
      return ret = 0.75 * fn(i + 1, j + 2) + 0.25 * fn(i + 1, j + 1);  
   };  
   cout.precision(15);  
   cout << fixed << fn(0, 0) << endl;  
}

Comments

You may also enjoy