Hdu 4734-F(x) 数位dp

showproblem.php?pid=4734

F(x)

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3347 Accepted Submission(s): 1258

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

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

3 0 100 1 10 5 100

Sample Output

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

Source

2013 ACM/ICPC Asia Regional Chengdu Online

Recommend

liuyiding | We have carefully selected several similar problems for you: 5664 5663 5662 5661 5660

题意：对于一个n位的十进制数x（A_nA_n-1……A₁），我们定义它的权重为：
　　F(x)=A_n*2^n-1+A_n-1*2^n-2+……+A₁*2⁰
　　现在，给你两个十进制数A和B，请计算出在闭区间[0, B]之中，有多少个数x的权重不大于A的权重，即F(x)<=F(A)。

题解：

数位dp

预处理出A的权重。f[i][j]为到第i位比j小的方案数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int DP[12][4616],digit[12];
 4 int read()
 5 {
 6     int s=0,fh=1;char ch=getchar();
 7     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
 8     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 9     return s*fh;
10 }
11 int GetFA(int k)
12 {
13     int sum=0,tmp=1;
14     while(k!=0)
15     {
16         sum+=(k%10)*tmp;k/=10;
17         tmp*=2;
18     }
19     return sum;
20 }
21 int Dfs(int len,int FA,int limit)
22 {
23     if(FA<0)return 0;
24     if(len<=0)return 1;
25     if(limit==0&&DP[len][FA]!=-1)return DP[len][FA];
26     int end=limit?digit[len]:9,ret=0,i;
27     for(i=0;i<=end;i++)ret+=Dfs(len-1,FA-i*(1<<(len-1)),limit&&(i==end));
28     if(limit==0)DP[len][FA]=ret;
29     return ret;
30 }
31 int Calc(int FA,int B)
32 {
33     int len=0;
34     memset(digit,0,sizeof(digit));
35     while(B!=0){digit[++len]=B%10;B/=10;}
36     return Dfs(len,FA,1);
37 }
38 int main()
39 {
40     int case1=0,A,B,FA,T;
41     T=read();
42     memset(DP,-1,sizeof(DP));
43     while(T--)
44     {
45         A=read();B=read();
46         FA=GetFA(A);
47         //memset(DP,-1,sizeof(DP));
48         printf("Case #%d: %d
",++case1,Calc(FA,B));
49     }
50     fclose(stdin);
51     fclose(stdout);
52     return 0;
53 }