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