問題
http://community.topcoder.com/stat?c=problem_statement&pm=12730&rd=15701
解き方
回文にするために一致させなければならアルファベットの集合を考えた時、
もっとも出現回数の大きいものだけを残して、他を変換するのが
一番コストをおさえられる。
あとは、上記の集合をしらべるのに無向グラフを利用すればよい。
コード
class GooseTattarrattatDiv1 {
public: int getmin(string S) {
int n=S.size();
int d[26][26],num[26],used[26];
memset(num,0,sizeof(num));
FORE(i,0,n)num[S[i]-'a']++;
memset(d,0,sizeof(d));
for(int i=0;i<n/2;i++){
d[S[i]-'a'][S[n-1-i]-'a']=1;
d[S[n-1-i]-'a'][S[i]-'a']=1;
}
FORE(k,0,26)FORE(i,0,26)FORE(j,0,26)d[i][j]|=(d[i][k] && d[k][j]);
int ret=0;
memset(used,0,sizeof(used));
FORE(i,0,26)if(!used[i]){
used[i]=1;
int sum=num[i],mx=num[i];
FORE(j,0,26)if(i!=j && d[i][j]){
mx=max(mx,num[j]);
sum+=num[j];
used[j]=1;
}
ret+=sum-mx;
}
return ret;
}
};
public: int getmin(string S) {
int n=S.size();
int d[26][26],num[26],used[26];
memset(num,0,sizeof(num));
FORE(i,0,n)num[S[i]-'a']++;
memset(d,0,sizeof(d));
for(int i=0;i<n/2;i++){
d[S[i]-'a'][S[n-1-i]-'a']=1;
d[S[n-1-i]-'a'][S[i]-'a']=1;
}
FORE(k,0,26)FORE(i,0,26)FORE(j,0,26)d[i][j]|=(d[i][k] && d[k][j]);
int ret=0;
memset(used,0,sizeof(used));
FORE(i,0,26)if(!used[i]){
used[i]=1;
int sum=num[i],mx=num[i];
FORE(j,0,26)if(i!=j && d[i][j]){
mx=max(mx,num[j]);
sum+=num[j];
used[j]=1;
}
ret+=sum-mx;
}
return ret;
}
};