問題
http://community.topcoder.com/stat?c=problem_statement&pm=8584&rd=12168
解き方
間隔が１からmaxPeriodについてそれぞれ最小の変換コストを検索し、
そのうち最小のものが答えになる。
コード
class DNAString {
public: int minChanges(int maxPeriod, vector<string> dna) {
string str=accumulate(all(dna),string());
int n=str.size();
int ret=1e+9;
for(int p=1;p<=maxPeriod;p++){
int cost=0;
for(int i=0;i<p;i++){
int a=0,t=0,g=0,c=0;
for(int j=i;j<n;j+=p){
if(str[j]=='A')a++;
else if(str[j]=='T')t++;
else if(str[j]=='G')g++;
else c++;
}
int mx=max(max(a,t),max(g,c));
cost+=a+t+c+g-mx;
}
ret=min(ret,cost);
}
return ret;
}
};
public: int minChanges(int maxPeriod, vector<string> dna) {
string str=accumulate(all(dna),string());
int n=str.size();
int ret=1e+9;
for(int p=1;p<=maxPeriod;p++){
int cost=0;
for(int i=0;i<p;i++){
int a=0,t=0,g=0,c=0;
for(int j=i;j<n;j+=p){
if(str[j]=='A')a++;
else if(str[j]=='T')t++;
else if(str[j]=='G')g++;
else c++;
}
int mx=max(max(a,t),max(g,c));
cost+=a+t+c+g-mx;
}
ret=min(ret,cost);
}
return ret;
}
};