AOJ - OCR

AOJ - OCR

이 문제는 꽤 난이도가 있다.

$dp[i][k]$ 를 $i$ 번째에 $k$ 번 째 단어를 뒀을 때, 끝까지 갈 때 가장 원문이 될 확률이 높은 값

이라고 하자.

사실 점화식 자체의 유도가 어렵진 않다 값이 복잡해서 그렇지

놀랐던건 종만북의 설명이 너무나 복잡하단 점이다.

void solve() {  
   int n, q;  
   cin >> n >> q;  
  
   vector<string> s(n);  
   fv(s);  
   map<string, int> idx;  
   for (int i = 0; i < n; i++) idx[s[i]] = i;  
  
   vector<double> start(n);  
   fv(start);  
  
   vector<vector<double>> nxt(n, vector<double>(n)), classify(n, vector<double>(n));  
   fv2(nxt);  
   fv2(classify);  
   while (q--) {  
      int m;  
      cin >> m;  
      vs t(m);  
      fv(t);  
  
      vector<vector<double>> dp(m, vector<double>(n, -1));  
      function<double(int, int)> fn = [&](int i, int k) -> double {  
         double &ret = dp[i][k];  
         if (ret > -0.5) return ret;  
         ret = 0;  
         if (i == m - 1) return ret = 1;  
         for (int j = 0; j < n; j++) {  
            ret = max(ret, nxt[k][j] * fn(i + 1, j) * classify[j][idx[t[i + 1]]]);  
         }  
         return ret;  
      };  
      vector<double> fi;  
      for (int i = 0; i < n; i++) {  
         fi.pb(fn(0, i) * start[i] * classify[i][idx[t[0]]]);  
      }  
      vector<string> ans;  
      function<void(int, int)> trace = [&](int i, int k) -> void {  
         ans.pb(s[k]);  
         if (i == m - 1)return;  
         for (int j = 0; j < n; j++) {  
            double tmp1 = fn(i, k);  
            double tmp = nxt[k][j] * fn(i + 1, j) * classify[j][idx[t[i + 1]]];  
            if (tmp1 == tmp) {  
               trace(i + 1, j);  
               break;  
            }  
         }  
      };  
  
      int initial = maxi(fi);  
      trace(0, initial);  
      for (string k: ans) cout << k << ' ';  
      cout << endl;  
   }  
}