sdnu 1248.B.陆历川玩数位 || HDU 4734 【数位dp】

1248.B.陆历川玩数位

Time Limit: 500 MS    Memory Limit: 131072 KB
Total Submission(s): 24    Accepted Submission(s): 12

Description

A number X have n digits(A1A2A3......An)

F(x) = A1*2n-1 + A2*2n-1 .....+An-1*21 + An *20

Now, give you two number A, B

You need to calculate how many number's F(x) is no more than F(A) between 0 to B

Input

T(0 < T<= 10000) T is TestCase

A, B (0 <= A, B <= 1000000000)

Output

Answer

Sample Input

1
1 1

Sample Output

Case #1: 2

Source

Unknown

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a,b,all;
int dp[15][100500];
int mx[15];
int dfs(int cnt,int sum,bool limit)
{
    if(cnt<0)return sum>=0;
    if(sum<0)return 0;
    if(!limit&&dp[cnt][sum]!=-1)return dp[cnt][sum];
    int up=limit?mx[cnt]:9;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        ans+=dfs(cnt-1,sum-i*(1<<cnt),limit&&i==up);
    }
    if(!limit)dp[cnt][sum]=ans;
    return ans;
}
int calc(int x)
{
    int cnt=0;
    while(x)
    {
        mx[cnt++]=x%10;
        x/=10;
    }
    return cnt;
}
int f(int x)
{
    int tmp=1;
    int ans=0;
    while(x)
    {
        ans+=x%10*tmp;
        tmp<<=1;
        x/=10;
//        cout<<tmp<<' '<<ans<<endl;
    }
    return ans;
}
int main()
{
    int t;
    int kcase=1;
    scanf("%d",&t);
    memset(dp,0xff,sizeof(dp));
    while(t--)
    {
        scanf("%d %d",&a,&b);
        all=f(a);
        printf("Case #%d: %d
",kcase++,dfs(calc(b)-1,all,1));
//        cout<<"Case #"<<kcase++<<": "<<dfs(calc(b)-1,all,1)<<'
';
    }
    return 0;
}