fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. using ll=long long;
  5.  
  6. const int inf=10000007;
  7.  
  8. int n,m,sm,pt,cnt[123][123],f[1050000][21];
  9. char s[100005];
  10. int O[1050000][21];
  11.  
  12. int dist(int mask, int k, int i)
  13. {
  14.     if(k==i) return __builtin_popcount(mask);
  15.     if(O[mask][i]==-1) return -1;
  16.     return dist((mask&(~(1<<i))),k,O[mask][i]);
  17. }
  18. int do_cham(int mask, int i, int j)
  19. {
  20.     int ans=0,bit1=__builtin_popcount(mask);
  21.     for(int k=0;k<pt;k++)
  22.     {
  23.         if(k==j) continue;
  24.         int temp=dist(mask,k,i);
  25.         if(temp!=-1)
  26.             ans+=(bit1+1-temp)*(cnt[j][k]+cnt[k][j]);
  27.     }
  28.     return ans;
  29. }
  30. int main()
  31. {
  32.     freopen("input_file.inp","r",stdin);
  33.     cin>>n>>m;
  34.     cin>>s[1];
  35.     sm=int(s[1]);
  36.     for(int i=2;i<=n;i++)
  37.     {
  38.         cin>>s[i];
  39.         if(s[i]!=s[i-1])
  40.             cnt[int(s[i-1])-97][int(s[i])-97]++;
  41.         sm=max(sm,int(s[i]));
  42.     }
  43.     pt=sm-96;
  44.     for(int mask=0;mask<(1<<pt);mask++)
  45.         for(int i=0;i<pt;i++)
  46.             f[mask][i]=inf;
  47.     for(int mask=0;mask<(1<<pt)-1;mask++)
  48.     {
  49.         if(!mask)
  50.         {
  51.             for(int i=0;i<pt;i++)
  52.             {
  53.                 f[mask|(1<<i)][i]=0;
  54.                 O[mask|(1<<i)][i]=-1;
  55.             }
  56.             continue;
  57.         }
  58.         for(int i=0;i<pt;i++)
  59.         {
  60.             for(int j=0;j<pt;j++)
  61.             {
  62.                 if(i==j) continue;
  63.                 if((mask&(1<<i)) && !(mask&(1<<j)))
  64.                 {
  65.                     int dc=do_cham(mask,i,j);
  66.                     if(f[mask][i]+dc<f[mask|(1<<j)][j])
  67.                     {
  68.                         f[mask|(1<<j)][j]=f[mask][i]+dc;
  69.                         O[mask|(1<<j)][j]=i;
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.     }
  75.     int ans=inf;
  76.     for(int i=0;i<pt;i++)
  77.         ans=min(ans,f[(1<<pt)-1][i]);
  78.     cout<<ans;
  79. }
  80.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
10000007
https://ideone.com/Su2zBD
KEYBOARD_HoMinhNhut
language:
C++14 (clang 8.0)
created:
5 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!