hdoj 4734 F(x)

题目链接：​​F(x)​​

题目大意：给你一个A和B现在有这样一个函数Function，他的作用是按位对每一个数算贡献，类似二进制，不过二进制的位是十进制的，比如234，则是2∗22+3∗21+4∗20，现在我们需要有一个初始的值Function（A），现在要求你去找到0到B之间有多少个数他的Function是不大于初始值的

题目思路：数位dp里面去剪枝，我们可以枚举数位然后用数位dp去判断这个数枚举的一些数已经超过初始值了，这样我们去给他减掉，那么剩下的就一定是成立的，这样去做就很轻松了

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
int digit[200],dp[200][30000],Sum;

int dfs(int pos,int sum,bool limit){
if(pos == -1) return sum >= 0?1:0;
if(sum < 0) return 0;
if(!limit&&dp[pos][sum] != -1) return dp[pos][sum];
int up = limit?digit[pos]:9;
int ans = 0;
for(int i = 0;i <= up;i++){
ans += dfs(pos-1,sum-(i*1<<pos),limit&&i == digit[pos]);
}
if(!limit) dp[pos][sum] = ans;
return ans;
}

int solve(int x){
int pos = 0;
while(x){
digit[pos++] = x%10;
x/=10;
}
return dfs(pos-1,Sum,true);
}

int Fun(int x){
int sum = 0,len = 0;
while(x){
sum += (x%10)*(1<<len);
x /= 10;
len++;
}
return sum;
}

int main(){
int t,A,B;
memset(dp,-1,sizeof(dp));
scanf("%d",&t);
int Case = 1;
while(t--){
scanf("%d%d",&A,&B);
Sum = Fun(A);
printf("Case #%d: %d\n",Case++,solve(B));
}
return 0;
}