fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e6 + 5;
  10. string s;
  11. int n, dp[N][5][5], change[N][5], cost[26][26], ans = 2e9;
  12.  
  13. void nhap() {
  14.     cin >> s;
  15.     n = s.size();
  16.     s = " " + s;
  17. }
  18.  
  19. void mn(int &a, int b) {
  20.     if (a > b) a = b;
  21. }
  22.  
  23. void backtrack(int pos, int t, string cur) {
  24.     if (pos > n) {
  25.         ans = min(ans, t);
  26.         return;
  27.     }
  28.  
  29.     FOR(i, 0, 25) {
  30.         char c = 'a' + i;
  31.         int len = cur.size();
  32.         if (len >= 1 && cur[len - 1] == c) continue;  
  33.         if (len >= 2 && cur[len - 2] == c) continue;
  34.  
  35.         backtrack(pos + 1, t + cost[::s[pos] - 'a'][i], cur + c);
  36.     }
  37. }
  38.  
  39. void trau() {
  40.     backtrack(1, 0, "");
  41.     cout << ans;
  42. }
  43.  
  44. void giai() {
  45.     memset(dp, 0x3f, sizeof dp);
  46.     FOR(i, 0, 25) FOR(j, 0, 25) cost[i][j] = min(abs(i - j), (26 - abs(i - j)) % 26);
  47.  
  48.     if (n <= 5) {
  49.         trau();
  50.         return;
  51.     }
  52.  
  53.     FOR(i, 1, n) FOR(j, -2, 2) change[i][j + 2] = (s[i] - 'a' + j + 26) % 26;
  54.     FOR(i, 0, 4) FOR(j, 0, 4) if (change[2][i] != change[1][j])
  55.         dp[2][i][j] = cost[s[2]- 'a'][change[2][i]] + cost[s[1] - 'a'][change[1][j]];
  56.  
  57.     FOR(i, 2, n - 1) FOR(j, 0, 4) FOR(k, 0, 4) if (change[i][j] != change[i - 1][k])
  58.         FOR(t, 0, 4) if (change[i + 1][t] != change[i][j] && change[i + 1][t] != change[i - 1][k])
  59.             mn(dp[i + 1][t][j], dp[i][j][k] + cost[s[i + 1] - 'a'][change[i + 1][t]]);
  60.  
  61.     FOR(i, 0, 4) FOR(j, 0, 4) if (change[n][i] != change[n - 1][j]) ans = min(ans, dp[n][i][j]);
  62.     cout << ans;
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(0);
  67.     cin.tie(0); cout.tie(0);
  68.  
  69.     #define name "removepalin"
  70.  
  71.     if (fopen(name".inp", "r")) {
  72.         freopen(name".inp", "r", stdin);
  73.         freopen(name".out", "w", stdout);
  74.     }
  75.  
  76.     nhap();
  77.     giai();
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.02s 101732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0bRBdW
language:
C++14 (clang 8.0)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!