sdnu 1248.B.陆历川玩数位

11 1

Case #1: 2

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[20][10002];//最大的时候也不是太大~开个10000+的数组就好了
int maxn[20];
int num;
int f(int x)//求他的f(x)是多少
{
	if (x == 0)
	{
		return 0;
	}
	int ans = f(x / 10);
	return ans * 2 + (x % 10);
}
int poww(int x)求这个2的x幂是多少
{
	int ans = 1;
	while (x--)
	{
		ans = ans * 2;
	}
	return ans;
}
int dfs(int pos, int sum, bool limit)进行dfs遍历
{
	if (pos == -1)如果f(x)>num;就不加入结果
	{
		return sum<=num;
	}
	if (sum > num)同上
	{
		return 0;
	}
	if (!limit&&dp[pos][num-sum] != -1)一定要注意边界的limit~所有的dp记忆化都要加上！limit
	{
		return dp[pos][num-sum];
	}
	int ans = 0;
	int up = limit ? maxn[pos] : 9;//查询上界
	for (int s = 0; s <= up; s++)
	{
		ans += dfs(pos - 1, (sum + poww(pos)*s), limit && (maxn[pos] == s));
	}
	if (!limit)
	{
		dp[pos][num-sum] = ans;记忆化
	}
	return ans;
}
int solve(int x)把边界储存下来；
{
	int pos = 0;
	while (x)
	{
		maxn[pos++] = x % 10;
		x = x / 10;
	}
	return dfs(pos - 1, 0, 1);
}
int main()
{
	memset(dp, -1, sizeof(dp));
	int te;
	scanf("%d", &te);
	int k = 1;
	while (te--)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		num = f(a);
		printf("Case #%d: %d\n",k++, solve(b));
	}
	return 0;
}