PKU 2038 Team Rankings

http://poj.org/problem?id=2038
n個のABCDEを並べ替えた文字列が与えられる。
このとき、ABCDEを並べ替えた文字列で、順番のずれがもっとも小さいもののうち、辞書順最小のものを出力しろというような問題。

順列を生成して、コスト計算して最小を出力

int n;

string in[1000];

int ranking[128];

void solve(){
  rep(i,n) cin >> in[i];

  pair<int,string> ans(10000,"");
  string a="ABCDE";
  
  do{
    int co=0;
    rep(i,5) ranking[a[i]] = i;
    
    rep(i,n)
      rep(j,5)rep(k,j)
      co += ranking[in[i][j]]<ranking[in[i][k]];

    ans=min(ans,mp(co,a));
  }while(next_permutation(ALL(a)));

  printf("%s is the median ranking with value %d.\n",ans.S.c_str(),ans.F);
}

main(){
  while(cin >> n, n) solve();
}