题目链接
F(x)
思路
一开始我是用前缀和分开，然后最后判断sum与f(a)的关系的，但是
后来我发现，如果我这样写，对于不同的f(a),需要不停的对dp数组重置为-1.
于是，我们必须要找到一个状态，与f(a)无关。所以我们可以把f(a)移项。
这样我们维护的就是sum-f(a)的值，并且对于每次搜索，我们只需要先把f(a)放进去。
然后出来的时候判断是否大于等于零即可
这样做的好处就是至于要对dp数组初始化一次即可，记忆化搜索可加速。
代码实现
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
50
51
52
53
54
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
int dp[20][200000];
int a[20];
int res=0;
int dfs(int pos,int sum,bool limit)
{
if(pos==-1)return sum>=0;
if(sum<0)return 0;
if(!limit&&dp[pos][sum]!=-1)return dp[pos][sum];
int up = limit?a[pos]:9;
int temp = 0;
for(int i=0;i<=up;i++)
{
temp += dfs(pos-1,sum-i*(1<<pos),limit&&i==up);
}
return limit?temp:dp[pos][sum]=temp;
}
int solve(ll x)
{
int p = 0;
while(x)
{
a[p++]=x%10;
x/=10;
}
return dfs(p-1,res,1);;
}
int cal(ll x)
{
int re = 0;
int tmp = 1;
while(x)
{
re+=x%10*tmp;
x/=10;
tmp*=2;
}
return re;
}
int main()
{
int t;
scanf("%d",&t);
memset(dp,-1,sizeof(dp));
for(int cas=1;cas<=t;cas++)
{
ll a,b;
scanf("%lld %lld",&a,&b);
res=cal(a);
printf("Case #%d: %lld\n",cas,solve(b));
}
}
|