hdu 4734 F(x) (数位dp)
题目链接s 题意：将一个10进制数x按照2进制展开后得到的值设为f(x)…现在给出a,b（10^9）问【0，b】中满足f[x]<=f[a]的数的个数。 思路：先算出f[a]…然后我们发现f(x)最大也就10*2^10=10240.。。数组可以存下。。搞之。和上一道题类似。。我们不关心两个f函数的值具体是多少。。。只关心他们的相对大小情况。。所以还是可以合并成一个变量。。。然而我用两个变量为什么错了。。不懂==
错误代码（用两个变量分别记录）
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月17日 星期四 21时30分57秒
4File Name :code/hdu/4734.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int a,b;
34int digit[15],digita[15];
35int fa;
36int dp[10][110000];//dp[i][j]表示长度为i,f[x]为j的方案数...
37int power[20];
38
39int cal( int n)
40{
41 ms(digita,0);
42 int len = 0 ;
43 while (n)
44 {
45 digita[++len] = n % 10;
46 n /= 10 ;
47 }
48 int base = 1;
49 int res = 0 ;
50 for ( int i = 1 ; i <= len ; i ++)
51 {
52// cout<<"digita:"<<digita[i]<<endl;
53 res +=digita[i]*base;
54 base*=2;
55 }
56
57 return res;
58}
59
60
61int dfs(int pos,int sum,bool limit)
62{
63 if (pos==0) return sum<=fa;
64 if (sum>fa) return 0; //sum只会越来越大。。所以这里可以减一下。。。
65 // if (sum+(power[pos+1]-1)*9<=fa) return 1; //如果后面的位置取最大仍然满足，可以提前就确定。减！
66 if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
67
68 int mx = limit?digit[pos]:9;
69
70 int res = 0 ;
71 for ( int i = 0 ; i <= mx ; i++)
72 {
73 res+=dfs(pos-1,sum+i*power[pos],limit&&i==mx);
74 }
75
76 // if (!limit) dp[pos][sum] = res;
77 return res;
78}
79int solve ( int n)
80{
81 ms(digit,0);
82 int len = 0 ;
83 while (n)
84 {
85 digit[++len] = n % 10;
86 n /= 10;
87 }
88
89 return dfs(len,0,true);
90}
91
92void pre()
93{
94 power[1] = 1;
95 for ( int i = 2 ; i <= 12 ; i++)
96 {
97 power[i] = power[i-1]*2;
98 }
99}
100int main()
101{
102 #ifndef ONLINE_JUDGE
103 freopen("code/in.txt","r",stdin);
104 #endif
105 pre();
106 int T;
107 cin>>T;
108 ms(dp,-1);
109 int cas = 0 ;
110 while (T--)
111 {
112 scanf("%d %d",&a,&b);
113 fa = cal(a);
114 int ans = solve(b);
115 printf("Case #%d: %d\n",++cas,ans);
116 }
117
118 #ifndef ONLINE_JUDGE
119 fclose(stdin);
120 #endif
121 return 0;
122}
AC代码：
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月18日 星期五 08时57分02秒
4File Name :code/hdu/r4734.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int digit[20];
34int a,b;
35int dp[11][11000];
36int power[15];
37int fa;
38int cal( int n)
39{
40// cout<<"n:"<<n;
41 int base = 1;
42 int res = 0 ;
43 while (n)
44 {
45 res += (n)*base;
46 base*=2;
47 n/=10;
48 }
49// cout<<" res:"<<res<<endl;
50 return res;
51}
52
53int dfs( int pos,int sum,bool limit) //依然是只关心两个数的相对大小。。。而不关心他们具体是多少。。
54{ //所以可以合并成一个变量。。。
55// cout<<"pos:"<<pos<<" sum:"<<sum<<endl;
56 if (pos==0) return sum>=0;
57 if (sum<0) return 0;
58
59 if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
60
61 int mx = limit? digit[pos] : 9 ;
62 int res = 0 ;
63 for ( int i = 0 ; i <= mx ; i++)
64 {
65 res+=dfs(pos-1,sum-power[pos]*i,limit&&i==mx);
66 }
67 if (!limit) dp[pos][sum] = res;
68 return res;
69}
70int solve ( int n )
71{
72 int len = 0 ;
73 ms(digit,0);
74 while (n)
75 {
76 digit[++len] = n % 10;
77 n/=10;
78 }
79// for ( int i = len ; i >=1 ; i--) cout<<digit[i];
80 return dfs(len,cal(a),true);
81}
82int main()
83 {
84 #ifndef ONLINE_JUDGE
85 freopen("code/in.txt","r",stdin);
86 #endif
87
88 power[1] = 1;
89 for ( int i = 2 ; i <= 12 ; i++) power[i] = power[i-1] * 2; //循环不小心从1开始。。。结果全0了。。。。2333
90 int T;
91 cin>>T;
92 int cas = 0;
93 ms(dp,-1);
94 while (T--)
95 {
96 scanf("%d %d",&a,&b);
97 fa = cal(a);
98 int ans = solve(b);
99 printf("Case #%d: %d\n",++cas,ans);
100
101 }
102
103 #ifndef ONLINE_JUDGE
104 fclose(stdin);
105 #endif
106 return 0;
107}