InTheBloodHorse

每日一题(11) HDU4734

字数统计: 316阅读时长: 1 min
2018/09/21 Share

题目地址
题意:
找出i在[0,b]的f(i)小于等于f(a)的数的个数。
思路:
还是数位dp。
关键点1:用dp[pos][sta]来保存位数为pos,f(number)为sta的个数
思考:为什么只需要初始化一次dp数组
答案:因为dp[pos][sta]和f(a)没有任何关系

关键点2:尝试用 f(a) 减去 f(number)来判断
比如:
pos : n-1位数字是由n位数字推出来的,所以减去2的n次方

有点绕了
AC代码:

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
#include<bits/stdc++.h>
using namespace std;
int a[20];
int dp[20][5000];
int maxn;
int dfs(int pos,int sta,bool lim){
if(pos<0) return sta>=0;
if(sta<0) return 0;
if(!lim && dp[pos][sta]!=-1) return dp[pos][sta];
int up = lim ? a[pos]:9;
int ans=0;
for(int i=0;i<=up;i++){
ans += dfs(pos-1,sta-i*(1<<(pos)),lim && i==a[pos]);
}
if(!lim) dp[pos][sta]=ans;
return ans;
}
int solve(int x){
int pos =0;
while(x){
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1,maxn,true);
}
int main()
{
int t;
int index=1;
scanf("%d",&t);
int x,y;
memset(dp,-1,sizeof(dp));
while(t--){
scanf("%d %d",&x,&y);
maxn = 0;
int cnt=0;
while(x){
maxn += (x%10)*(1<<(cnt++));
x/=10;
}
printf("Case #%d: %d\n",index++,solve(y));
}
}

原文作者:InTheBloodHorse

原文链接:http://pyking.cn/2018/09/21/每日一题-11-HDU4734/

发表日期:September 21st 2018, 9:31:51 pm

更新日期:September 21st 2018, 9:54:21 pm

版权声明:Have a fun

CATALOG