なんとか完答。
https://www.hackerrank.com/contests/unkoder-07/challenges/ab-warp
問題
A,Bで構成されたN文字の文字列がある。
先頭の文字から初めて、1手で隣接する位置か、同じ文字の位置にワープできる。
最後の文字に到達するので最小何手かかるか。
解法
愚直にDPで最小値を求めるだけ。
実際は同じ文字のうち一番後ろに存在するものか、もしくは次の文字に移動するかの2択なのでO(N)で解けるが、以下は移動先を全部チェックしているのでO(N^2)。
int L; string S; int step[101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>S; L=S.size(); FOR(i,100) step[i]=1010; step[0]=0; FOR(i,L) { step[i+1]=min(step[i+1],step[i]+1); for(j=i+1;j<L;j++) if(S[i]==S[j]) step[j]=min(step[j],step[i]+1); } cout<<step[L-1]<<endl; }
まとめ
まだウォームアップ。