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; }};