SRM572 Div2 Medium "NextOrPrev"
問題
文字列に対し、下記の2つの操作を行える
Ope "Next" : 'z'以外の文字を1つ選び、その文字を次のように変える。(a->b b->c c->d ... )
Ope "Prev" : 'a'以外の文字を1つ選び、その文字を次のように変える。(z->y y->x x->w ... )
例)
aabc -> 操作 "Next" 'b' -> aacc
aabc -> 操作 "Prev" 'b' -> aaac
aabc -> 操作 "Next" 'a' -> bbbc
操作Nextにかかる費用、Prevにかかる費用が与えられている。
文字列startから文字列goalへ、費用が最小になるよう
2つの操作を行った時、その費用を返せ。
startからgoalへ変換できないときは-1を返せ。
また、startとgoalには同じ文字が2つ以上含んでいない。
制約
1 <= Next,Prevのコスト <= 1000
1 <= start,goalの文字数 <= 26
考えた事
a -> d
e -> c
みたいに、NextとPrevの操作で範囲が重なってしまうとダメ
a -> d
c -> e
みたいに、Next同士の操作だったら範囲が重なってもいい
あれ?NextとPrevの操作で範囲が重なるから
いったんPrevで逃がしといて、
Nextで持っていくみたいな操作って意味ないよね?
ってことは、最小費用になるか、変換できないか、になるな。
あれ?最後のSample通らない・・・
あ、
a -> e
b -> c
みたいに、同じ操作でも追い越さなきゃいけないようなのはダメだ~
ソースコード
class NextOrPrev { public: int getMinimum(int nextCost, int prevCost, string start, string goal){ int n = start.length(); for( int i = 0; i < n; i++ ){ for( int j = i + 1; j < n; j++ ){ int si = start[i], gi = goal[i], sj = start[j], gj = goal[j]; if( si > gi ) swap( si, gi ); if( sj > gj ) swap( sj, gj ); if( si < sj && gj < gi ) return -1; if( sj < si && gi < gj ) return -1; } } int dr[26]; fill( dr, dr + 26, 0 ); int res = 0; for( int i = 0; i < n; i++ ){ int d = 1; int s = start[i] - 'a'; int e = goal[i] - 'a' - 1; int cost = nextCost; if( start[i] > goal[i] ){ d = -1; e = start[i] - 'a' - 1; s = goal[i] - 'a'; cost = prevCost; } for( int i = s; i <= e; i++ ){ if( dr[i] != 0 && dr[i] != d ){ return -1; } dr[i] = d; } res += ( e - s + 1 ) * cost; } return res; } };