For a decimal number x with n digits (A nA n-1A n-2 ... A 2A 1), we define its weight as F(x) = A n * 2 n-1 + A n-1 * 2 n-2 + ... + A 2 * 2 + A 1 * 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).
题目链接🔗
题解
数位DP
先可以得到状态转移方程
我们设 dp[i][j] 为长度为 i , f[x] 值小于 j 的个数
假设第 i 位为 k ,那么长度 i-1 的数都满足 ,然后只需要求出 , 当 k 为 0 是需要特判处理,因为它少一位的数不一定小于原数
防止超时,在搜索过程中用上记忆化
代码
#include <cstdio>
#include <cstring>
using namespace std;
int t,dp[15][10005],arr[15];
int dfs(int len,int x,int flag)
{
if(len == 0) return x>=0;
if(x < 0) return 0;
if(!flag&&dp[len][x]!=-1) return dp[len][x];
int ans = 0, end = flag?arr[len]:9;
for(int i=0;i<=end;i++)
ans += dfs(len-1,x - i*(1<<(len-1)),flag&&i==end);
if(!flag) dp[len][x] = ans;
return ans;
}
int f(int x)
{
int ans = 0,i=0;
while(x) ans+=(x%10)*(1<<i),i++,x/=10;
return ans;
}
int solve(int x,int y)
{
int i=0;
while(y)arr[++i] = y%10,y/=10;
return dfs(i,f(x),1);
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
scanf("%d",&t);memset(dp,-1,sizeof(dp));
for(int i=1;i<=t;i++)
{
int a,b;
scanf("%d %d",&a,&b);
printf("Case #%d: %d\n",i,solve(a,b));
}
return 0;
}