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函数的值具体是多少。。。只关心他们的相对大小情况。。所以还是可以合并成一个变量。。。然而我用两个变量为什么错了。。不懂==
错误代码（用两个变量分别记录）
/* ***********************************************
Author :111qqz
Created Time :2016年03月17日 星期四 21时30分57秒
File Name :code/hdu/4734.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int a,b;
7int digit[15],digita[15];
8int fa;
9int dp[10][110000];//dp[i][j]表示长度为i,f[x]为j的方案数...
10int power[20];
1int cal( int n)
2{
3 ms(digita,0);
4 int len = 0 ;
5 while (n)
6 {
7 digita[++len] = n % 10;
8 n /= 10 ;
9 }
10 int base = 1;
11 int res = 0 ;
12 for ( int i = 1 ; i <= len ; i ++)
13 {
14// cout<<"digita:"<<digita[i]<<endl;
15 res +=digita[i]*base;
16 base*=2;
17 }
return res;
}
1int dfs(int pos,int sum,bool limit)
2{
3 if (pos==0) return sum<=fa;
4 if (sum>fa) return 0; //sum只会越来越大。。所以这里可以减一下。。。
5 // if (sum+(power[pos+1]-1)*9<=fa) return 1; //如果后面的位置取最大仍然满足，可以提前就确定。减！
6 if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
int mx = limit?digit[pos]:9;
1 int res = 0 ;
2 for ( int i = 0 ; i <= mx ; i++)
3 {
4 res+=dfs(pos-1,sum+i*power[pos],limit&&i==mx);
5 }
1 // if (!limit) dp[pos][sum] = res;
2 return res;
3}
4int solve ( int n)
5{
6 ms(digit,0);
7 int len = 0 ;
8 while (n)
9 {
10 digit[++len] = n % 10;
11 n /= 10;
12 }
return dfs(len,0,true);
}
1void pre()
2{
3 power[1] = 1;
4 for ( int i = 2 ; i <= 12 ; i++)
5 {
6 power[i] = power[i-1]*2;
7 }
8}
9int main()
10{
11 #ifndef ONLINE_JUDGE
12 freopen("code/in.txt","r",stdin);
13 #endif
14 pre();
15 int T;
16 cin>>T;
17 ms(dp,-1);
18 int cas = 0 ;
19 while (T--)
20 {
21 scanf("%d %d",&a,&b);
22 fa = cal(a);
23 int ans = solve(b);
24 printf("Case #%d: %d\n",++cas,ans);
25 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
AC代码：
/* ***********************************************
Author :111qqz
Created Time :2016年03月18日 星期五 08时57分02秒
File Name :code/hdu/r4734.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int digit[20];
7int a,b;
8int dp[11][11000];
9int power[15];
10int fa;
11int cal( int n)
12{
13// cout<<"n:"<<n;
14 int base = 1;
15 int res = 0 ;
16 while (n)
17 {
18 res += (n)*base;
19 base*=2;
20 n/=10;
21 }
22// cout<<" res:"<<res<<endl;
23 return res;
24}
1int dfs( int pos,int sum,bool limit) //依然是只关心两个数的相对大小。。。而不关心他们具体是多少。。
2{ //所以可以合并成一个变量。。。
3// cout<<"pos:"<<pos<<" sum:"<<sum<<endl;
4 if (pos==0) return sum>=0;
5 if (sum<0) return 0;
if (!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
1 int mx = limit? digit[pos] : 9 ;
2 int res = 0 ;
3 for ( int i = 0 ; i <= mx ; i++)
4 {
5 res+=dfs(pos-1,sum-power[pos]*i,limit&&i==mx);
6 }
7 if (!limit) dp[pos][sum] = res;
8 return res;
9}
10int solve ( int n )
11{
12 int len = 0 ;
13 ms(digit,0);
14 while (n)
15 {
16 digit[++len] = n % 10;
17 n/=10;
18 }
19// for ( int i = len ; i >=1 ; i--) cout<<digit[i];
20 return dfs(len,cal(a),true);
21}
22int main()
23 {
24 #ifndef ONLINE_JUDGE
25 freopen("code/in.txt","r",stdin);
26 #endif
1 power[1] = 1;
2 for ( int i = 2 ; i <= 12 ; i++) power[i] = power[i-1] * 2; //循环不小心从1开始。。。结果全0了。。。。2333
3 int T;
4 cin>>T;
5 int cas = 0;
6 ms(dp,-1);
7 while (T--)
8 {
9 scanf("%d %d",&a,&b);
10 fa = cal(a);
11 int ans = solve(b);
12 printf("Case #%d: %d\n",++cas,ans);
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}