HDU - 4734 F(x)

思路：

数位dp。dp[i][j]中i表示第i位，j表示当最高位为i时的和。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int a[15], dp[15][5000];
int A, B;
int dfs(int pos, int sum, bool limit)
{
    if (pos < 0) 
	{
		return sum >= 0 ;
	}
    if (sum < 0) 
	{
		return 0;
	}
    if (!limit && dp[pos][sum] != -1) 
	{
		return dp[pos][sum];
	}
    int up = limit ? a[pos] : 9;
	int result = 0;
    for (int i = 0; i <= up; i++)
	{
         result += dfs(pos - 1, sum - i * (1 << pos), limit && i == a[pos]);
	}

    if (!limit) 
	{
		dp[pos][sum] = result;
	}

    return result;
}

int F(int x)
{
    int sum = 0;
	int base = 1;
	while (x > 0)
	{
		sum += (x % 10) * base;
		base <<= 1;
		x /= 10;
	}

    return sum; 
}

int solve(int x, int y)
{
    int pos = 0;
    while (x > 0)
	{
		a[pos] = x % 10;
		x /= 10;
		pos++;
	}

	return dfs(pos - 1, F(y), 1);
}

int main()
{
    int T;
    memset(dp, -1, sizeof(dp));
    scanf( "%d", &T);
    for (int i = 1; i <= T; i++)
	{
        scanf( "%d%d", &A, &B);
        printf("Case #%d: %d\n", i, solve(B, A));
    }

    return 0;
}