CFR 489 C. Given Length and Sum of Digits... ( DP )

Problem - C - Codeforces
題意：
給 M ( 數字長度 )，S ( 位數總和 )，求可能構造之最小數及最大數，或判定不可構造。
解法：
由於數據範圍不大，所以狀態設計成長度相同時比較，就可以直接用 string 和內建字典序比較進行 DP。
dp[ i ][ j ] : 已有 i 位數，位數總和為 j 的情況下，已 string 描述的最小/大數

int M, S;

void init(){
	cin >> M >> S;
}

void preprocess(){
	for( int i = 0; i < M + 1; ++i )
		SINF += "9";
}

void solve(){
	if( S == 0 ){
		if( M == 1 )
			cout << "0 0" << endl;
		else
			cout << "-1 -1" << endl;
	} else{
		vector< vector< string > > dpmin( M + 1, vector< string >( S + 1, SINF ) );
		dpmin[ 0 ][ S ] = "";
		vector< vector< string > > dpmax( M + 1, vector< string >( S + 1, NSINF ) );
		dpmax[ 0 ][ S ] = "";
		for( int i = 0; i < M; ++i )
			for( int j = 0; j <= S; ++j )
				for( int d = ( i == 0 ); d <= min( 9, j ); ++d )
					upmin( dpmin[ i + 1 ][ j - d ], dpmin[ i ][ j ] + ( char )( '0' + d ) ),
					upmax( dpmax[ i + 1 ][ j - d ], dpmax[ i ][ j ] + ( char )( '0' + d ) );
		if( dpmin[ M ][ 0 ] == SINF or dpmax[ M ][ 0 ] == NSINF )
			cout << "-1 -1" << endl;
		else
			cout << dpmin[ M ][ 0 ] << " " << dpmax[ M ][ 0 ] << endl;
	}
}