SRM509 Div1 Medium(500) PalindromizationDiv1

PalindromizationDiv1

文字列を回文にする編集回数は、文字列を２つに分けて左側と右側をひっくり返したものの編集距離を求めれば良い。左側に文字aが、右側にbがあるとき、一致させるためには、aからもbからも変換可能なある文字cがあれば良い。追加も消去も空白を文字と見なせばまとめて扱える。

#include <string>
#include <vector>
#include <sstream>
using namespace std;

const long long INF = 0x1000000000000ll;

vector<vector<long long> >warshall_floyd(vector<vector<long long> >E)
{
    int n=(int)E.size();
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)
        E[j][k]=min(E[j][k],E[j][i]+E[i][k]);
    return E;
}

long long editdistance( string a, string b, vector<vector<long long> > cost )
{
    int n=(int)a.length();
    int m=(int)b.length();

    vector<vector<long long> >T(n+1,vector<long long>(m+1,INF));

    T[0][0] = 0;
    for(int i=1;i<=n;i++)
        T[i][0] = min( T[i][0], T[i-1][0]+cost[0][a[i-1]] );
    for(int j=1;j<=m;j++)
        T[0][j] = min( T[0][j], T[0][j-1]+cost[0][b[j-1]] );

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        T[i][j] = min( T[i][j], T[i  ][j-1]+cost[0     ][b[j-1]] );
        T[i][j] = min( T[i][j], T[i-1][j  ]+cost[a[i-1]][0     ] );
        T[i][j] = min( T[i][j], T[i-1][j-1]+cost[a[i-1]][b[j-1]] );
    }

    return T[n][m];
}

string rev( string w )
{
    return string(w.rbegin(),w.rend());
}

class PalindromizationDiv1{public:
int getMinimumCost( string word, vector <string> operations )
{
    vector<vector<long long> > tmp( 128, vector<long long>( 128, INF ) );
    for ( int i=0; i<(int)operations.size(); i++ )
    {
        stringstream ss(operations[i]);
        char c1, c2; int x; string t;
        switch ( operations[i][0] )
        {
        case 'a': ss>>t>>c1>>x;     tmp[0][c1]=x;   break;
        case 'e': ss>>t>>c1>>x;     tmp[c1][0]=x;   break;
        case 'c': ss>>t>>c1>>c2>>x; tmp[c1][c2]=x;  break;
        }
    }
    for ( int i=0; i<128; i++ )
        tmp[i][i] = 0;
    tmp = warshall_floyd( tmp );

    vector<vector<long long> > cost( 128, vector<long long>( 128, INF ) );
    for ( int i=0; i<128; i++ )
    for ( int j=0; j<128; j++ )
    for ( int k=0; k<128; k++ )
        cost[i][j] = min( cost[i][j], tmp[i][k]+tmp[j][k] );

    long long ans = INF;

    int n = (int)word.length();
    for ( int i=0; i<=n; i++ )
        ans = min( ans,
            editdistance( word.substr(0,i), rev(word.substr(i)), cost ) );
    for ( int i=0; i<n; i++ )
        ans = min( ans,
            editdistance( word.substr(0,i), rev(word.substr(i+1)), cost ) );

    return (int)(ans<INF ? ans : -1);
}};