「 HDU P4734 」 F(x)

# 题目大意

对于一个数 $x$，它的每一位数字分别是 $A_{n}A_{n-1}A_{n-2}\cdots A_{2}A_{1}$，定义其权重 $f(x)=\sum_{i=1}^{n}\left(A_i\times 2^{i-1}\right)$。

现在给定两个数 $A,B$ 求出 $[0,B]$ 中满足 $f(i)\le f(A)$ 的数的个数。

# 解题思路

数位 $\text{DP}$。

我一开始设的状态是 $dp[i][j]$ 表示到第 $i$ 位，并且现在已经枚举到的数位的权重是 $j$，写完之后发现会 $\text{TLE}$，因为相对与每组数据来说它们的 $A$ 不是一样的，按上面的状态设计方程会导致记忆化下来的答案并不是通用的，需要每次都 $memset$ $dp$ 数组。

然后考虑另一种状态，另第一维的意义不变，将第二维变成剩余的可用权值(大体就是那么个意思)，然后做记忆化。

# 附上代码

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int a, b, pow[], T, dp[][], cnt, num[], fa;

inline void init() {

    pow[] = ;

    for(int i=; i<=; i++) pow[i] = pow[i-] * ;

}

inline int dfs(int l, int f, bool limit) {

    if(dp[l][f] && !limit) return dp[l][f];

    if(l == ) return f >= ;

    int ans = , mx = limit ? num[l] : ;

    for(int i=; i<=mx; i++) {

        if(f - i * pow[l-] < ) continue;

        ans += dfs(l-, f-i*pow[l-], limit && i==mx);

    }

    return (!limit) ? dp[l][f]=ans : ans;

}

inline int solve(int x) {

    int k = ;

    while (x) {

        num[++k] = x % ;

        x /= ;

    }

    return dfs(k, fa, true);

}

inline void fff(int x) {

    fa = ;

    int k = ;

    while (x) {

        fa += pow[k] * (x % );

        k ++;

        x /= ;

    }

}

int main() {

    init();

    scanf("%d", &T);

    while (T--) {

        scanf("%d%d", &a, &b);

        fff(a);

        printf("Case #%d: %d\n", ++cnt, solve(b));

    }

}

巴特西

「 HDU P4734 」 F(x)

# 题目大意

# 解题思路

# 附上代码

最新文章

热门文章