首页 > 代码库 > hdu 4734 F(x) 数位DP
hdu 4734 F(x) 数位DP
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4734
题意:
我们定义十进制数x的权值为f(x) = a(n)*2^(n-1)+a(n-1)*2(n-2)+...a(2)*2+a(1)*1,a(i)表示十进制数x中第i位的数字。题目给出a,b,求出0~b有多少个不大于f(a)的数。
思路:
数位dp,还是这个博客:http://blog.csdn.net/wust_zzwh/article/details/52100392
dp[pos][sum]:=sum不是存当前枚举的数的前缀和(加权的),而是枚举到当前pos位,后面还需要凑sum的权值和的个数,也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值,显然sum=0时就是满足的,后面的位数凑足sum位就可以了。
这个是一种优化,多组case,最初在外面初始化dp为-1就行了,因为不同的case,每个数的信息是不变的,之前计算的dp值无论在哪组case都是这个答案,直接返回就行,这也是为什么定义sum为还需要凑的数,如果定义sum为到当前位的权值和,那么每个高位的数都不一样,所以每组case都要初始化一遍dp为-1,还要重新计算每一个dp值,会TLE
下面是评论里的解释:题目要求f[i]=f[a]变成f[a]-f[i]=0;相当于初始值为f[a],只要能减到0就是合法状态。,之所以与f[a]无关:假设先输入一个a,且f(a)=10,dfs记录了一个状态dp[3][10]=5,表示枚举到pos=3时还需要减掉10才能合法的状态有5个(也可以说与目标0的差值是10),那么下一次输入b,且f(b)=20,还是从高位开始枚举,恰好枚举到pos=3,且还需要交掉10才能合法的状态,也就是dp[3][10],这个时候上一次记录的状态依然是可以用的啊,因为都是到了pos=3的位置,都是还需要减掉10就能达到最后的目标,所以这个子问题就重叠了。
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 int A,B,k,a[20],dp[20][maxn]; 19 20 int f(int x){ 21 if(x == 0) return 0; 22 int ans = f(x/10); 23 return ans*2+x%10; 24 } 25 26 int dfs(int pos,int sum,int limit){ 27 if(pos==-1) return sum<=k; 28 if(sum > k) return 0; 29 if(!limit && dp[pos][k-sum]!=-1) return dp[pos][k-sum]; 30 int up = limit ? a[pos] : 9; 31 int re = 0; 32 for(int i=0; i<=up; i++){ 33 re += dfs(pos-1,sum+i*(1<<(pos)),limit&&i==a[pos]); 34 } 35 if(!limit) dp[pos][k-sum] = re; 36 return re; 37 } 38 39 int solve(int x){ 40 int pos = 0; 41 while(x){ 42 a[pos++] = x%10; 43 x /= 10; 44 } 45 46 int re = dfs(pos-1,0,true); 47 return re; 48 } 49 50 int main(){ 51 int T = read(); 52 memset(dp,-1,sizeof(dp)); 53 int cas=1; 54 while(T--){ 55 cin >> A >> B; 56 k = f(A); 57 int ans = solve(B); 58 printf("Case #%d: %d\n",cas++,ans); 59 } 60 61 return 0; 62 }
hdu 4734 F(x) 数位DP