読者です 読者をやめる 読者になる 読者になる

kyos1704活動記

適当に考えたことや調べたことを垂れ流すものです。質問等ありましたらtwitter:@kyos1704 に質問してください。

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

あとはできることがわかっているので
一個ずつ足してやれば良い