# 题目大意
对于一个数 $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[
15], T, dp[
15][
10003], cnt, num[
15], fa;
inline void init() {
pow[0] =
1;
for(
int i=
1; i<=
10; i++) pow[i] = pow[i-
1] *
2;
}
inline int dfs(
int l,
int f,
bool limit) {
if(dp[l][f] && !limit)
return dp[l][f];
if(l ==
0)
return f >=
0;
int ans =
0, mx = limit ? num[l] :
9;
for(
int i=
0; i<=mx; i++
) {
if(f - i * pow[l-
1] <
0)
continue;
ans += dfs(l-
1, f-i*pow[l-
1], limit && i==
mx);
}
return (!limit) ? dp[l][f]=
ans : ans;
}
inline int solve(
int x) {
int k =
0;
while (x) {
num[++k] = x %
10;
x /=
10;
}
return dfs(k, fa,
true);
}
inline void fff(
int x) {
fa =
0;
int k =
0;
while (x) {
fa += pow[k] * (x %
10);
k ++
;
x /=
10;
}
}
int main() {
init();
scanf("%d", &
T);
while (T--
) {
scanf("%d%d", &a, &
b);
fff(a);
printf("Case #%d: %d\n", ++
cnt, solve(b));
}
}
转载于:https://www.cnblogs.com/bljfy/p/9657349.html
