SRM556 Div2 Hard(1000) LeftRightDigitsGame

LeftRightDigitsGame

動的計画法。digitsのi文字目まで使ったときに、位置pから始まる最小の文字列を覚えておく。

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

class LeftRightDigitsGame{public:
string minNumber( string digits )
{
    int n = (int)digits.size();

    vector<string> T(n,"z");
    for ( int p=0; p<n; p++ )
        if ( p==0 && digits[0]!='0' || 0<p )
            T[p] = min( T[p], string(1,digits[0]) );

    for ( int i=1; i<n; i++ )
    {
        vector<string> P = T;
        T = vector<string>(n,"z");

        for ( int p=0; p<n-i; p++ )
        {
            if ( P[p+1]!="z" &&
                 ( p==0 && digits[i]!='0' || 0<p ) )
                T[p] = min( T[p], digits[i]+P[p+1] );

            if ( P[p]!="z" )
                T[p] = min( T[p], P[p]+digits[i] );
        }
    }

    return T[0];
}};