SRM556 Div1 Medium(500) LeftRightDigitsGame2

LeftRightDigitsGame2

AがBより大きいということと、次の条件を満たす整数cp(0≦cp≦|A|)が存在することは、同値である。

i<cp ⇒ A[i]==B[i] ∧ i==cp ⇒ A[i]>B[i]

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

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

class LeftRightDigitsGame2{public:
string minNumber( string digits, string lowerBound )
{
    string ans = "z";
    int n = (int)digits.size();

    for ( int cp=0; cp<=n; cp++ )
    {
        vector<string> T(n,"z");
        for ( int p=0; p<n; p++ )
            if ( p<cp && digits[0]==lowerBound[p] ||
                 p==cp && digits[0]>lowerBound[p] ||
                 p>cp )
                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<cp && digits[i]==lowerBound[p] ||
                       p==cp && digits[i]>lowerBound[p] ||
                       p>cp ) )
                    T[p] = min( T[p], digits[i]+P[p+1] );

                if ( P[p]!="z" &&
                     ( p+i<cp && digits[i]==lowerBound[p+i] ||
                       p+i==cp && digits[i]>lowerBound[p+i] ||
                       p+i>cp ) )
                    T[p] = min( T[p], P[p]+digits[i] );
            }
        }

        ans = min( ans, T[0] );
    }

    return ans=="z" ? "" : ans;
}};