F(x) 数位dp

佚名 6年前 (2019-04-16) 随笔 928人围观抢沙发百度已收录

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])

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 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\n",++kase,solve(b));
    }
    return 0;
}