fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ii pair<int,int>
  5. #define iii pair<int, ii>
  6. #define fi first
  7. #define se second
  8. #define inf 10000000000000000
  9. int n, m;
  10. string s;
  11. int ts[30][30];
  12. int f[(1<<20)+5];
  13. signed main() {
  14.     ios_base::sync_with_stdio(0);
  15.     cin.tie(0);
  16.     cout.tie(0);
  17.     if(fopen("main.inp","r")) {
  18.         freopen("main.inp", "r", stdin);
  19.         freopen("main.out", "w", stdout);
  20.     }
  21.     cin >> n >> m;
  22.     cin >> s;
  23.     for(int i = 1; i < n; i++) {
  24.         int kt = s[i]-'a';
  25.         int kt2 = s[i-1] - 'a';
  26.         ts[kt][kt2]++;
  27.         ts[kt2][kt]++;
  28.     }
  29.     for(int i = 1; i < (1<<m); i++) f[i] = inf;
  30.     for(int mask = 0; mask < (1<<m); mask++) {
  31.         for(int i = 0; i < m; i++) {
  32.             if(mask & (1<<i)) {
  33.                 int val = 0;
  34.                 int z = __builtin_popcount(mask);
  35.                 for(int j = 0; j < m; j++) {
  36.                     if(j != i) {
  37.                         if(mask & (1<<j)) val += z*ts[i][j];
  38.                         else val -= z*ts[i][j];
  39.                     }
  40.                 }
  41.                 f[mask] = min(f[mask],f[mask^(1<<i)] + val);
  42.             }
  43.         }
  44.     }
  45.     cout << f[(1<<m)-1];
  46.     return 0;
  47. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VwJwHw
language:
C++14 (gcc 8.3)
created:
1 day 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!