fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define nmax 20
  4. #define inf 1e9
  5.  
  6. int N, M;
  7. string S;
  8. vector<char> letters;
  9. unordered_map<char, int> freq;
  10. int dist[nmax][nmax], dp[1 << nmax][nmax];
  11.  
  12. int solve()
  13. {
  14.     int fullMask = (1 << M) - 1;
  15.     for (int mask = 0; mask < (1 << M); mask++)
  16.         fill(dp[mask], dp[mask] + M, inf);
  17.  
  18.     for (int i = 0; i < M; i++)
  19.         dp[1 << i][i] = 0;
  20.  
  21.     for (int mask = 1; mask < (1 << M); mask++)
  22.     {
  23.         for (int last = 0; last < M; last++)
  24.         {
  25.             if (!(mask & (1 << last)))
  26.                 continue;
  27.             for (int next = 0; next < M; next++)
  28.             {
  29.                 if (mask & (1 << next))
  30.                     continue;
  31.                 int newMask = mask | (1 << next);
  32.                 dp[newMask][next] = min(dp[newMask][next], dp[mask][last] + dist[last][next]);
  33.             }
  34.         }
  35.     }
  36.  
  37.     int res = inf;
  38.     for (int i = 0; i < M; i++)
  39.         res = min(res, dp[fullMask][i]);
  40.     return res;
  41. }
  42.  
  43. int main()
  44. {
  45.     ios::sync_with_stdio(0);
  46.     cin.tie(0);
  47.     freopen("sapphim.inp", "r", stdin);
  48.     freopen("sapphim.out", "w", stdout);
  49.     cin >> N >> M >> S;
  50.  
  51.     for (char c : S)
  52.         freq[c]++;
  53.     for (auto p : freq)
  54.         letters.push_back(p.first);
  55.  
  56.     M = letters.size();
  57.     if (M == 1)
  58.     {
  59.         cout << 0 << "\n";
  60.         return 0;
  61.     }
  62.  
  63.     sort(letters.begin(), letters.end());
  64.     int ans = inf;
  65.  
  66.     do
  67.     {
  68.         unordered_map<char, int> pos;
  69.         for (int i = 0; i < M; i++)
  70.             pos[letters[i]] = i;
  71.  
  72.         memset(dist, 0, sizeof dist);
  73.         for (int i = 0; i < M; i++)
  74.             for (int j = 0; j < M; j++)
  75.                 dist[i][j] = abs(i - j);
  76.  
  77.         int cost = 0;
  78.         for (int i = 0; i < N - 1; i++)
  79.             cost += dist[pos[S[i]]][pos[S[i + 1]]];
  80.  
  81.         ans = min(ans, cost);
  82.     } while (next_permutation(letters.begin(), letters.end()));
  83.  
  84.     cout << ans << "\n";
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/V7CysG
language:
C++ (gcc 8.3)
created:
11 days 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!