AOJ - NUMB3RS - 두니아 박사의 탈옥

AOJ - NUMB3RS

예전에 종만북을 공부할 때 어렵게 풀었던 문제같은데(못풀었었나?) 다시 푸니 쉽게 풀려 감회가 새롭다.

$\quad dp[i][day]=$ 현재 $i$ 마을에 있고 $day$ 일이 지난 시점일 때 $0$일에 $p$마을에 있을 확률

이라고 두고,

$$ dp[i][day]=\begin{cases}\displaystyle\sum_{p \to i}\left( \dfrac {dp[p][day-1]}{p\text{마을에서 갈 수 있는 마을 개수}} \right) \\ 1~(day=0~\&~i=p) \\ 0~(day=0~\&~i\ne p) \end{cases} $$

라고 두고 푼다.

시간 복잡도는 $O(n^2d)$

void solve() {  
   int n, d, p, t;  
   cin >> n >> d >> p;  
   vvi g(n, vi(n));  
   fv2(g);  
   cin >> t;  
   vi q(t), cnt(n);  
   fv(q);  
   for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (g[i][j]) cnt[i]++;  
  
   vector<vector<double>> dp(n + 1, vector<double>(d + 5, -1));  
   function<double(int, int)> fn = [&](int i, int day) -> double {  
      if (day == 0) return i == p;  
      double &ret = dp[i][day];  
      if (ret > -0.5) return ret;  
      ret = 0;  
      for (int j = 0; j < n; j++) {  
         if (g[j][i]) {  
            ret += 1.0 / cnt[j] * fn(j, day - 1);  
         }  
      }  
      return ret;  
   };  
  
   cout.precision(15);  
   for (int x: q) cout << fixed << fn(x, d) << ' ';  
   cout << endl;  
}