AOJ - PI

AOJ - PI

열심히 $O(N)$ DP 를 구현해주면 된다.

void solve() {  
   string s;  
   cin >> s;  
   int n = sz(s);  
   s = " " + s;  
   vi dp(n + 1, 1e15);  
   dp[0] = 0;  
  
   auto check2 = [&](string s) -> int {  
      bool f = 1;  
      for (int i = 1; i < sz(s); i++) {  
         if (s[i] != s[i - 1] + 1) f = 0;  
      }  
      if (f) return 1;  
      f = 1;  
      for (int i = 1; i < sz(s); i++) {  
         if (s[i] != s[i - 1] - 1) f = 0;  
      }  
      return f;  
   };  
  
   for (int i = 3; i <= n; i++) {  
      {  
         string sub = s.substr(i - 2, 3);  
         if (cntt(sub, sub[0]) == 3) {  
            dp[i] = min(dp[i], dp[i - 3] + 1);  
         } else if (check2(sub)) {  
            dp[i] = min(dp[i], dp[i - 3] + 2);  
         } else if (sub[0] == sub[2]) {  
            dp[i] = min(dp[i], dp[i - 3] + 4);  
         } else if (sub[1] - sub[0] == sub[2] - sub[1]) {  
            dp[i] = min(dp[i], dp[i - 3] + 5);  
         } else {  
            dp[i] = min(dp[i], dp[i - 3] + 10);  
         }  
      }  
  
      if (i >= 4) {  
         string sub = s.substr(i - 3, 4);  
         if (cntt(sub, sub[0]) == 4) {  
            dp[i] = min(dp[i], dp[i - 4] + 1);  
         } else if (check2(sub)) {  
            dp[i] = min(dp[i], dp[i - 4] + 2);  
         } else if (sub[0] == sub[2] && sub[1] == sub[3]) {  
            dp[i] = min(dp[i], dp[i - 4] + 4);  
         } else if (sub[1] - sub[0] == sub[2] - sub[1] && sub[2] - sub[1] == sub[3] - sub[2]) {  
            dp[i] = min(dp[i], dp[i - 4] + 5);  
         } else {  
            dp[i] = min(dp[i], dp[i - 4] + 10);  
         }  
      }  
  
      if (i < 5) continue;  
      {  
         string sub = s.substr(i - 4, 5);  
         if (cntt(sub, sub[0]) == 5) {  
            dp[i] = min(dp[i], dp[i - 5] + 1);  
         } else if (check2(sub)) {  
            dp[i] = min(dp[i], dp[i - 5] + 2);  
         } else if (sub[0] == sub[2] && sub[0] == sub[4] && sub[1] == sub[3]) {  
            dp[i] = min(dp[i], dp[i - 5] + 4);  
         } else if (sub[1] - sub[0] == sub[2] - sub[1] && sub[2] - sub[1] == sub[3] - sub[2]  
            && sub[3] - sub[2] == sub[4] - sub[3]) {  
            dp[i] = min(dp[i], dp[i - 5] + 5);  
         } else {  
            dp[i] = min(dp[i], dp[i - 5] + 10);  
         }  
      }  
   }  
   cout << dp[n] << endl;  
}