F(x) 数位dp

Problem 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[sup]9[/sup])

Output

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

Sample Input

3 0 100 1 10 5 100

Sample Output

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

其实转化后的数字比原来的要小得多一开始还纠结开不起数组　　

把数位的和保存起来最后读取完的时候再比较即可

为了memset优化 dp数组用减法

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
#define N 20

int f(int x)
{
    if(!x)return 0;
    int ans=f(x/10);
    return ans*2+(x%10);
}

ll dp[20][10000+5];
ll a[N];
int all;

ll dfs(int pos,int sum,bool lead,bool limit)
{
    if(!pos)
    {
       return sum<=all;
    }
    if(sum>all)return 0;

    if(!limit&&!lead&&dp[pos][all-sum]!=-1)return dp[pos][all-sum];
    ll ans=0;
    int up=limit?a[pos]:9;
    rep(i,0,up)
    {
      ans+=dfs(pos-1, sum+i*(1<<pos-1)  ,   lead&&i==0,limit&&i==a[pos]);

    }

    if(!limit&&!lead)dp[pos][all-sum]=ans;
    return ans;
}
ll solve(int b)
{
    int pos=0;

    while(b)
    {
        a[++pos]=b%10;
        b/=10;
    }

    return dfs(pos, 0 ,true,true);
}
int main()
{
    CLR(dp,-1);
    
    RI(cas);
    int kase=0;
    while(cas--)
    {
        int  a,b;
        cin>>a>>b;
        all=f(a);
        printf("Case #%d: %lld
",++kase,solve(b));
    }
    return 0;
}

View Code