問題
ある文字列が与えられ、それを回文にしたい。
回文にするために複数のアルファベットの追加、削除、変換式が与えられ、各変換式について必要なコストも与えられる。
このとき、回文にするために必要な最小のコストを求める。回文にできないときはー１を返す。
解き方
Editorialを読みました。
通常の回文の解き方をベースに、それを応用できるか。
通常の回文の解き方は以下の通り。
左端と右端の場所が一致、もしくは残り１文字になれば終了。
そうでなければいずれかの操作を行う。
１）回分の左端と右端(a,b-1)のアルファベットがことなれば一致するように変換し、
変換コストを足して(a+1,b-2)を調べる。
２）左端を削除し、削除コストを足して(a+1,b-1)を調べる。
３）右端を削除し、削除コストを足して（a,b-2）を調べる。
今回はコストの考え方について応用する。
削除については、アルファベットを空白に変換と考えれば変換と同様に操作できる。
同様に追加についても、空白をアルファベットに変換と考えることができる。
上記の操作によって、変換のコストだけをコードに落とせればよい。
変換のコストは問題で与えられるので、配列に保存してからワーシャルフロイドを回して任意の２つのアルファベットの最小の変換コストを求める。
ただし今回は、変換できればよいことから
あるアルファベットa→c とb→cのコストの和が最小であれば上記に置き換える必要がある。
また、例外の判定については定義したＩＮＦの和が発生しうるため、
オーバーフローしないように値の判定と更新を行うことに注意。
コード
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()
const int INF=1000000000;
string word;
int d[27][27],m[27][27],dp[51][51];
class PalindromizationDiv1 {
public:
int rec(int a,int b){
if(dp[a][b]!=-1)return dp[a][b];
if(a==b||a==b-1)return 0;
int ret=INF;
int c1=word[a]-'a',c2=word[b-1]-'a';
int cost1=rec(a+1,b-1);
int cost2=m[c1][c2];
if(ret-cost1>cost2)ret=cost1+cost2;
cost1=rec(a+1,b);
cost2=m[26][c1];
if(ret-cost1>cost2)ret=cost1+cost2;
cost1=rec(a,b-1);
cost2=m[26][c2];
if(ret-cost1>cost2)ret=cost1+cost2;
return dp[a][b]=ret;
}
int getMinimumCost(string word_, vector<string> operations) {
word=word_;
FORE(i,0,27)FORE(j,0,27)d[i][j]= i==j ? 0 : INF;
FORE(i,0,27)FORE(j,0,27)m[i][j]=INF;
memset(dp,-1,sizeof(dp));
FORE(i,0,operations.size()){
string str;
char c1,c2;
stringstream out(operations[i]);
out>>str>>c1;
if(str=="erase"){
out>>d[c1-'a'][26];
}
else if(str=="add"){
out>>d[26][c1-'a'];
}
else{
out>>c2;
out>>d[c1-'a'][c2-'a'];
}
}
FORE(k,0,27)FORE(i,0,27)FORE(j,0,27)if(d[i][k]!=INF&&d[k][j]!=INF)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
FORE(i,0,27)FORE(j,0,27)FORE(k,0,27)if(d[i][k]!=INF&&d[j][k]!=INF)m[i][j]=min(m[i][j],d[i][k]+d[j][k]);
int ret=rec(0,word.size());
return ret>=INF ? -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()
const int INF=1000000000;
string word;
int d[27][27],m[27][27],dp[51][51];
class PalindromizationDiv1 {
public:
int rec(int a,int b){
if(dp[a][b]!=-1)return dp[a][b];
if(a==b||a==b-1)return 0;
int ret=INF;
int c1=word[a]-'a',c2=word[b-1]-'a';
int cost1=rec(a+1,b-1);
int cost2=m[c1][c2];
if(ret-cost1>cost2)ret=cost1+cost2;
cost1=rec(a+1,b);
cost2=m[26][c1];
if(ret-cost1>cost2)ret=cost1+cost2;
cost1=rec(a,b-1);
cost2=m[26][c2];
if(ret-cost1>cost2)ret=cost1+cost2;
return dp[a][b]=ret;
}
int getMinimumCost(string word_, vector<string> operations) {
word=word_;
FORE(i,0,27)FORE(j,0,27)d[i][j]= i==j ? 0 : INF;
FORE(i,0,27)FORE(j,0,27)m[i][j]=INF;
memset(dp,-1,sizeof(dp));
FORE(i,0,operations.size()){
string str;
char c1,c2;
stringstream out(operations[i]);
out>>str>>c1;
if(str=="erase"){
out>>d[c1-'a'][26];
}
else if(str=="add"){
out>>d[26][c1-'a'];
}
else{
out>>c2;
out>>d[c1-'a'][c2-'a'];
}
}
FORE(k,0,27)FORE(i,0,27)FORE(j,0,27)if(d[i][k]!=INF&&d[k][j]!=INF)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
FORE(i,0,27)FORE(j,0,27)FORE(k,0,27)if(d[i][k]!=INF&&d[j][k]!=INF)m[i][j]=min(m[i][j],d[i][k]+d[j][k]);
int ret=rec(0,word.size());
return ret>=INF ? -1 : ret;
}
};