HDU 4734 F(x)(数位DP) - c++编程基础

Description

For a decimal number x with n digits (A _nA _n-1A _n-2 ... A ₂A ₁), we define its weight as F(x) = A _n * 2 ^n-1 + A _n-1 * 2 ^n-2 + ... + A ₂ * 2 + A ₁ * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 10 ⁹)

Output

For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.

Sample Input

Sample Output

 Case #1: 1
Case #2: 2
Case #3: 13

简单的数位DP：先将A表示成F(x)然后统计有多少大于x就行了。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; typedef pair
             
              pil; const int INF = 0x3f3f3f3f; int t,temp; LL l,r; int num[20]; LL dp[20][20000]; LL dfs(int pos,int sum,int flag) { if(pos==0) return sum>=0; if(sum<0) return 0; if(!flag&&dp[pos][sum]!=-1) return dp[pos][sum]; LL ans=0; int ed=flag?num[pos]:9; for(int i=0;i<=ed;i++) { int s=sum-i*(1<<(pos-1)); ans+=dfs(pos-1,s,flag&&i==ed); } if(!flag) dp[pos][sum]=ans; return ans; } LL solve(LL x) { int pos=0; while(x) { num[++pos]=x%10; x/=10; } return dfs(pos,temp,1); } LL work(LL x) { LL ans=0; int l=0; while(x) { ans+=(x%10)*(1<