题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25909
思路：好久没接触数位dp了=.=!，搞了这么久！一类记忆化搜索。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define FILL(a,b) memset(a,b,sizeof(a)) 7 typedef long long ll; 8 9 ll dp[33][2][33]; 10 int n,digit[33]; 11 12 13 ll dfs(int pos,int pre,int sum,int doing) 14 { 15 if(pos==-1)return sum; 16 if(!doing&&dp[pos][pre][sum]!=-1)return dp[pos][pre][sum]; 17 ll ans=0; 18 int end=doing?digit[pos]:1; 19 for(int i=0;i<=end;i++){ 20 ans+=dfs(pos-1,i,sum+(pre==i&&i==1),doing&&i==end); 21 } 22 if(!doing)dp[pos][pre][sum]=ans; 23 return ans; 24 } 25 26 ll Solve(int n) 27 { 28 int pos=0; 29 while(n){ 30 digit[pos++]=(n&1); 31 n>>=1; 32 } 33 return dfs(pos-1,0,0,1); 34 } 35 36 int main() 37 { 38 FILL(dp,-1); 39 int _case,t=1; 40 scanf("%d",&_case); 41 while(_case--){ 42 scanf("%d",&n); 43 printf("Case %d: %lld ",t++,Solve(n)); 44 } 45 return 0; 46 }