SRM490 Div1 Medium(550) QuickT9

QuickT9

Dが空文字列になったときで区切って考える。それぞれの文字列は数字を1回以上、その後Rightを1回かCを1回以上入力して得られる文字列。各文字列について最小タイプ数を求めて、動的計画法。

#include <vector>
#include <string>
#include <map>
#include <set>
#include <sstream>

using namespace std;

vector<string> dic;     //  辞書
vector<string> digit;   //  辞書の入力に必要なキーストローク
map<string,int> type;   //  添字の入力に必要なタイプ数

void BT( string D )
{
    int l = (int)D.length();

    //  validな文字列
    set<string> U;
    for ( int i=0; i<(int)dic.size(); i++ )
        if ( digit[i].length() >= D.length()  &&
             digit[i].substr(0,l) == D )
            U.insert( dic[i].substr(0,l) );
    
    //  validな文字列それぞれに対して
    //  Right もしくは C を連打したときの文字列とタイプ数を求める
    int c = 0;
    for ( set<string>::iterator u=U.begin(); u!=U.end(); u++, c++ )
        for ( int i=1; i<=l; i++ )
        {
            string s = u->substr(0,i);  
            int t = i==l ? l+c+1 : l+c+(l-i);
            if ( type.count(s) == 0  ||
                 type[s] > t )
                type[s] = t;
        }

    //  validな文字列がまだあれば探索
    if ( U.size() > 0 )
        for ( int i=2; i<=9; i++ )
            BT( D + char('0'+i) );
}

class QuickT9{public:
int minimumPressings( vector <string> t9, string word )
{
    //  辞書
    dic.clear();
    for ( int i=0; i<(int)t9.size(); i++ )
    {
        stringstream ss( t9[i] );
        string d;
        while ( ss >> d )
            dic.push_back( d );
    }

    //  キーストローク
    int button[26] = { 2,2,2, 3,3,3, 4,4,4, 5,5,5,
                       6,6,6, 7,7,7,7, 8,8,8, 9,9,9,9 };
    digit.clear();
    for ( int i=0; i<(int)dic.size(); i++ )
    {
        digit.push_back( "" );
        for ( int j=0; j<(int)dic[i].length(); j++ )
            digit.back() += char( '0' + button[dic[i][j]-'a'] );
    }

    //  辞書の部分文字列の打つのに必要な最小タイプ数を求める
    type.clear();
    for ( int i=2; i<=9; i++ )
        BT( string(1,'0'+i) );

    //  DP
    int n = word.size();
    int inf = 99999999;
    vector<int> T( n+1, inf );  //  wordの先頭i文字の入力に必要なタイプ数
    T[0] = 0;
    for ( int i=1; i<=n; i++ )
        for ( int j=0; j<i; j++ )
        {
            string s = word.substr(j,i-j);
            if ( type.count(s) > 0 )
                T[i] = min( T[i], T[j]+type[s] );
        }

    return T[n]<inf ? T[n] : -1;
}};