发现和自己以前写的数位DP不一样，用记忆化搜索实现改变边界的多次查询。
# 题面
> Linked HDU 4734
点击展开/折叠题面
给你两个数 $A,B$，定义一种函数 $F(x)$，设 $x$ 的数位第 $i$ 位（从第 $0$ 位开始）为 $x_i$，则
$$F(x)=\sum2^ix_i$$
求满足 $x\in[0,B]$ 且 $F(x)\le F(A)$ 的 $x$ 的数量。
多组询问。
# 解析
显然是数位DP，然后又发现 $F(x)$ 最大（即 $F(10^9-1)$）才 $4599$，于是可以定义状态：f[i][j][0/1] 表示前 $i$ 位确定、此时 $F(x)=j$、后面的数位是否受到限制的方案数。
状态数是 $10^5$，可以轻松跑过一次查询，但是查询有 $10^4$ 就会 TLE 了（而且时限还是 500ms QwQ）。
考虑另外一种记忆化搜索实现的数位DP，并且改变状态定义：f[i][j] 表示考虑了前 $i$ 位，第 $i$ 位已经不受数位限制，且 $F(x)\le i$ 的方案数。
注意到我们只储存了第 $i$ 位不受限制的答案，而受限制的每次询问要重新计算。
这种做法的正确性显然，但是为什么时间复杂度也正确？
当一个位置受限制，当且仅当更高位的每一位都相同，其实这样的状态只有 $len$ 个（$len$ 是 $x$ 的数位长度），于是在计算出一次 DP 值过后，每次只会额外计算不超过 $10$ 次，在多次询问时表现得非常优秀。
# 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4600;
int dig[11];
int f[11][N];
inline int Ri(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
return r;
}
int Calc(int x){
int ret=0,per=1;
while(x){
ret+=x%10*per;
x/=10,per<<=1;
}
return ret;
}
int DFS(int i,int j,bool lim){
if(i<1) return j>=0;
if(j<0) return 0;
if(!lim && (~f[i][j])) return f[i][j];
int lk=lim? dig[i]:9;
int ans=0;
for(int k=0;k<=lk;k++)
ans+=DFS(i-1,j-(1<<(i-1))*k,lim&&k==lk);
if(!lim) f[i][j]=ans;
return ans;
}
int Solve(int A,int B){
int n=0;
while(B) dig[++n]=B%10,B/=10;
return DFS(n,Calc(A),true);
}
int main(){
memset(f,-1,sizeof f);
for(int ca=1,cas=Ri();ca<=cas;ca++){
int A=Ri(),B=Ri();
printf("Case #%d: %d\n",ca,Solve(A,B));
}
return 0;
}
|
THE END
Thanks for reading!
> Linked 朝汐-网易云