fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ii pair<ll,ll>
  5. #define vi vector<ll>
  6. #define pb push_back
  7. #define all(s) s.begin(), s.end()
  8. #define fi first
  9. #define se second
  10. const int N=(1<<20);
  11. const ll Mod=1e9+7, oo=1e18;
  12. int n, m, dp[N+5], f[25][25];
  13. string s;
  14. signed main()
  15. {
  16.     //Nothing beats a Jet-2 Holiday!
  17.     //And right now, you can save 50 pounds per person.
  18.     //That's 200 pounds for a family of 4!
  19.     freopen("keyboard.inp", "r", stdin); freopen("keyboard.out", "w", stdout);
  20.     ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL);
  21.     cin>>n>>m>>s;
  22.     for(int i=0; i+1<s.size(); i++) 
  23.         f[s[i]-'a'][s[i+1]-'a']++, f[s[i+1]-'a'][s[i]-'a']++;
  24.     fill(dp+1, dp+(1<<m), 1e9);
  25.     for(int msk=1; msk<(1<<m); msk++) {
  26.         int pos=__builtin_popcount(msk);
  27.         for(int i=0; i<m; i++) if((msk>>i)&1) {
  28.             int mask=msk^(1<<i), c=dp[mask];
  29.             for(int j=0; j<m; j++) if(j!=i) {
  30.                 if((msk>>j)&1) c+=f[i][j]*pos; 
  31.                 else c-=f[i][j]*pos;
  32.             }
  33.             dp[msk]=min(dp[msk], c);
  34.         }
  35.     }
  36.     cout<<dp[(1<<m)-1];
  37.     return 0;
  38. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uj7EFD
language:
C++14 (gcc 8.3)
created:
4 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!