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

题目链接🔗

HDU-4734 F(x)

题解

数位DP
先可以得到状态转移方程
我们设 dp[i][j] 为长度为 i , f[x] 值小于 j 的个数
假设第 i 位为 k ,那么长度 i-1 的数都满足 x[0,B]x \in [0,B] ,然后只需要求出 1kdp[len1][ji(1<<(len1))]\sum_{1}^{k}dp[len-1][j-i \cdot (1<<(len-1))] , 当 k0 是需要特判处理,因为它少一位的数不一定小于原数
防止超时,在搜索过程中用上记忆化

代码

#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;
}