HDU 4734 F(x)——数位dp

时间:2022-12-16 10:36:52

题意:找出i在0到b之间的f(i)小于等于f(a)的数的个数。

思路:数位dp。主要在于状态转移不好想。dp[i][j]表示i位数比j小的数的个数。用递归完成的话就只需要思考边界和状态转移。

边界:

dp[i][j]如果j小于0,显然是dp[i][j]=0的,如果i==0,说明就是0,显然任何数都比0大,所以dp[i][j]对于j>=0的时候dp[i][j]=1,否则dp[i][j]=0

状态转移:

dp[i][j]+=dp[i-1][j-k*(1<<(i-1))];

完成上述两步推导就能开始写这题了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5000;
ll a, b;
int num[32];
ll dp[32][maxn];
int f(ll x) {
    int ans = 0, pos = 0;
    while (x) {
        ans += (x%10) * (1<<pos);
        pos++;
        x /= 10;
    }
    return ans;
}
ll dfs(int pos, int state, bool limit, bool lead) {
    if (pos == -1) return (state >= 0);
    if (state < 0) return 0;
    if (!limit && !lead && ~dp[pos][state]) return dp[pos][state];
    int up = (limit ? num[pos] : 9);
    ll ans = 0;
    for (int i = 0; i <= up; i++) {
        ans += dfs(pos-1, state-i*(1<<(pos)), limit && i == num[pos], lead && i == 0);
    }
    if (!limit && !lead) dp[pos][state] = ans;
    return ans;
}
ll solve(ll x) {
    int pos = 0;
    while (x) {
        num[pos++] = x % 10;
        x /= 10;
    }
    return dfs(pos-1, f(a), true, true);
}
int main() {
    int T;
    scanf("%d", &T);
    memset(dp, -1, sizeof(dp));
    for (int kase = 1; kase <= T; kase++) {
        scanf("%lld%lld", &a, &b);
        printf("Case #%d: %lld\n", kase, solve(b));
    }
    return 0;
}