SRM579 Div1 Easy(250), Div2 Medium(550) UndoHistory

TopCoder

UndoHistory

貪欲法。不要な文字をundoに作るくらいなら、必要なときに作れば良い。

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

int pref( string a, string b )
{
    a += "!";
    b += "?";
    for ( int i=0; ; i++ )
        if ( a[i]!=b[i] )
            return i;
    return -1;
}

class UndoHistory{public:
int minPresses( vector <string> lines )
{
    int ans = (int)lines[0].size()+1;

    for ( int i=1; i<(int)lines.size(); i++ )
    {
        int a = 1000000000;
        //  bufferを使う
        if ( pref(lines[i-1],lines[i])==(int)lines[i-1].size() )
            a = min( a, (int)lines[i].size()-(int)lines[i-1].size()+1 );
        //  undoを使う
        for ( int j=0; j<i; j++ )
            a = min( a, 2+(int)lines[i].size()-pref(lines[j],lines[i])+1 );
        ans += a;
    }

    return ans;
}};