問題
http://topcoder.bgcoder.com/print.php?id=2146
0と１からなる文字列が２つ与えられ、１つ目の文字列を２つ目の文字列に変換したい。
変換する方法として、文字列のi番目とj番目を選ぶことでそのサブ文字列を反対にすることができる。
このとき、文字列を変換するのに最小の変換回数を求める。
ただし、変換できないときはー１を返す。
解き方
文字列の最初と最後に着目し、そこが同じであればその場所については交換しなくてもよい。
つまり、ｄｆｓを用いて最初が一緒のときはその文字を削除し次の走査に入り、
最後の文字についても同様。
どちらのケースもない場合は交換が必要だが、上記に当てはまらない場合は文字をすべてひっくり返すしか選択しはない。そのためすべてひっくり返し、上記の場合を調べる。
ｄｐの状態はサブ文字列とした箇所とひっくり返したかどうかなので、メモ化することで計算量も間に合う。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
map<string,int> m;
class ReversalChain {
public:
int calc(string init,string goal){
if(init==goal)return 0;
int n=init.size();
string str=init+' '+goal;
if(m.find(str)!=m.end())return m[str];
int ret=10000;
if(init[0]==goal[0])ret=min(ret,calc(init.substr(1),goal.substr(1)));
if(init[n-1]==goal[n-1])ret=min(ret,calc(init.substr(0,n-1),goal.substr(0,n-1)));
for(int i=0;i<n-1-i;i++)swap(init[i],init[n-1-i]);
if(init[0]==goal[0])ret=min(ret,1+calc(init.substr(1),goal.substr(1)));
if(init[n-1]==goal[n-1])ret=min(ret,1+calc(init.substr(0,n-1),goal.substr(0,n-1)));
return m[str]=ret;
}
int minReversal(string init, string goal) {
m.clear();
int ret=calc(init,goal);
return ret==10000 ? -1 : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
map<string,int> m;
class ReversalChain {
public:
int calc(string init,string goal){
if(init==goal)return 0;
int n=init.size();
string str=init+' '+goal;
if(m.find(str)!=m.end())return m[str];
int ret=10000;
if(init[0]==goal[0])ret=min(ret,calc(init.substr(1),goal.substr(1)));
if(init[n-1]==goal[n-1])ret=min(ret,calc(init.substr(0,n-1),goal.substr(0,n-1)));
for(int i=0;i<n-1-i;i++)swap(init[i],init[n-1-i]);
if(init[0]==goal[0])ret=min(ret,1+calc(init.substr(1),goal.substr(1)));
if(init[n-1]==goal[n-1])ret=min(ret,1+calc(init.substr(0,n-1),goal.substr(0,n-1)));
return m[str]=ret;
}
int minReversal(string init, string goal) {
m.clear();
int ret=calc(init,goal);
return ret==10000 ? -1 : ret;
}
};