hdu4734---F(x)(디지털 dp)

Problem Description For a decimal number x with n digits (AnAn-1An-2 … A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + … + A2 * 2 + A1 * 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 < 109)
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: 5177 5173 5169 5168 5165
dp[i][j]를 설정하면 i 자릿수를 표시하고 F 값은 j의 개수보다 작다

/************************************************************************* > File Name: hdu4734.cpp > Author: ALex > Mail: [email protected] > Created Time: 2015 02 26      13 17 59  ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

int FA;
int dp[15][10000];
int bit[15];

int dfs (int cur, int e, int k, bool flag, bool zero)
{
    if (k < 0)
    {
        return 0;
    }
    if (cur == -1)
    {
        return 1;
    }
    if (!flag && ~dp[cur][k])
    {
        return dp[cur][k];
    }
    int ans = 0;
    int end = flag ? bit[cur] : 9;
    for (int i = 0; i <= end; ++i)
    {
        if (zero && !i)
        {
            ans += dfs (cur - 1, 0, k, flag && (i == end), 1);
        }
        else
        {
            ans += dfs (cur - 1, i, k - i * (1 << cur), flag && (i == end), 0);
        }
    }
    if (!flag)
    {
        dp[cur][k] = ans;
    }
    return ans;
}

int calc (int n)
{
    int cnt = 0;
    while (n)
    {
        bit[cnt++] = n % 10;
        n /= 10;
    }
    return dfs (cnt - 1, 0, FA, 1, 1);
}

int main ()
{
    int t;
    int icase = 1;
    scanf("%d", &t);
    memset (dp, -1, sizeof(dp));
    while (t--)
    {
        int cnt = 0;
        int a, b;
        scanf("%d%d", &a, &b);
        while (a)
        {
            bit[cnt++] = a % 10;
            a /= 10;
        }
        FA = 0;
        for (int i = 0; i < cnt; ++i)
        {
            FA += bit[i] * (1 << i);
        }
        printf("Case #%d: ", icase++);
        printf("%d
", calc (b));
    }
    return 0;
}