经过这几题 我发现数位dp 主要是 dp[pos][count][pre]这个设定,看到位置pos的时候 哪些状态能够影响之后的解 比方说 这题如果没了pre 就不对了 因为到pos时 有count的区非 也有pre的区分!!!!如果没有了pre那么只计算了其中一种情况(具体哪一种识具体题目而定,但不要纠结这个)
AC代码如下:
#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; int digit[33]; long long dp[33][33][2]; long long DFS( int pos, int count, int pre, bool limit ){ if( pos <= 0 ){ return count; } if( !limit && dp[pos][count][pre] != -1 ){ return dp[pos][count][pre]; } int end = limit ? digit[pos] : 1; long long sum = 0; for( int i = 0; i <= end; i++ ){ int temp = count; if( pre == 1 && i == 1 ){ temp++; } sum += DFS( pos - 1, temp, i, limit && i == end ); } if( !limit ){ dp[pos][count][pre] = sum; } return sum; } long long solve( int N ){ for( int i = 0; i < 32; i++ ){ if( ( 1 << i ) & N ){ digit[i+1] = 1; }else{ digit[i+1] = 0; } } int len = 32; while( digit[len] == 0 && len > 0 ){ len--; } return DFS( len, 0, 0, true ); } int main(){ int T, Case = 1; int N; cin >> T; memset( dp, -1, sizeof( dp ) ); while( T-- ){ cin >> N; cout << "Case " << Case++ << ": " <<solve( N ) << endl; } return 0; }