CFR 204 A. Little Elephant and Interval ( Digit DP )

Problem - 204A - Codeforces
題意：
求 [ l, r ] 中，第一個位數等於最後一個位數的數字數量。
解法：
dp[ i ][ j ][ k ][ l ] : 考慮前 i 個位數，已嚴格小於對照數，第一個位數，最後一個位數，滿足這些條件的狀態數。
注意當 k == 0 的時候若要轉移，那麼該轉移數就是它的第一位數。

ll L, R;

void init(){
	cin >> L >> R;
}

void preprocess(){

}

ll get_pcnt( ll x, int inc ){ // returns number of the required values in range [ 1, x ) / ]
	vi s;
	while( x )
		s.emplace_back( x % 10 ),
		x /= 10;
	reverse( s.begin(), s.end() );
	vvvvl dp( s.size() + 1, vvvl( 2, vvl( 10, vl( 10 ) ) ) );
	dp[ 0 ][ 0 ][ 0 ][ 0 ] = 1;
	for( int i = 0; i < s.size(); ++i )
		for( int j = 0; j < 2; ++j )
			for( int k = 0; k < 10; ++k )
				for( int l = 0; l < 10; ++l )
					for( int d = 0; d <= ( j ? 9 : s[ i ] ); ++d ){
						if( k == 0 )
							dp[ i + 1 ][ j | d < s[ i ] ][ d ][ d ] += dp[ i ][ j ][ k ][ l ];
						else
							dp[ i + 1 ][ j | d < s[ i ] ][ k ][ d ] += dp[ i ][ j ][ k ][ l ];
					}
	ll res = 0;
	for( int j = 0; j < 2; ++j )
		for( int k = 1; k < 10; ++k ){
			if( not j and not inc )
				continue;
			res += dp[ ( int ) s.size() ][ j ][ k ][ k ];
		}
	return res;
}

void solve(){
	cout << get_pcnt( R, 1 ) - get_pcnt( L, 0 );
}