SRM572 Div2 Medium(500) NextOrPrev
ae→{0,1}, acb→{0,2,1}のように、各文字の文字列中での順位を表す配列を考える。startとgoalでの配列が一致していれば変換可能、一致していなければ途中で同じ文字になってしまうので不可能。変換可能なら貪欲に変換すれば良い。
#include <string> #include <vector> using namespace std; // 各文字の文字列中での辞書順を返す vector<int> Rank( string w ) { int n = (int)w.size(); vector<int> R(n); for ( int i=0; i<n; i++ ) for ( int j=0; j<n; j++ ) if ( w[j]<w[i] ) R[i]++; return R; } class NextOrPrev{public: int getMinimum( int nextCost, int prevCost, string start, string goal ) { if ( Rank(start)!=Rank(goal) ) return -1; int ans = 0; for ( int i=0; i<(int)start.size(); i++ ) { if ( start[i]<goal[i] ) ans += nextCost*(goal[i]-start[i]); if ( start[i]>goal[i] ) ans += prevCost*(start[i]-goal[i]); } return ans; }};