SRM 572 - med - 500
問題
文字をずらして
目的の文字列に変形する
変形にはコストがかかるので
そのコストの最小値を求める
不可能なときは-1を返す
変換規則
char++ or char--
'a-z'の範囲内で移動
文字列中の同じ文字が一度に移動する
#include <string> #include <vector> #include<deque> #include<stack> #include<queue> #include<cmath> #include<utility> #include<iostream> using namespace std; class NextOrPrev { public: bool J(string s, string g){ int size=s.size(); for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ if(i!=j && (( (s[i]<s[j]&&g[i]<g[j])||(s[i]>s[j]&&g[i]>g[j]) ) == false ) ){ cout<<i<<" "<<j<<endl; return false; } } } return true; } int ANS(int nextCost, int prevCost, string start, string goal){ int ans=0; for(int i=0;i<start.size();i++){ while(start[i]!=goal[i]){ if(start[i]<goal[i]){ start[i]++; ans+=nextCost; }else if(start[i]>goal[i]){ start[i]--; ans+=prevCost; } } } return ans; } int getMinimum(int nextCost, int prevCost, string s, string g) { if(J(s,g)){ return ANS(nextCost,prevCost,s,g); }else{ return -1; } } };
解法
この変換規則において変換可能なときは
変形時に同じ文字が出現しなければよい
s[i]→s[j]
g[i]→g[j]
の→が両方一致するとき可能
可能じゃない時を弾きたいのでfalse
あとはできることがわかっているので
一個ずつ足してやれば良い