【HDU4734】F(x) 【数位dp】

时间:2022-12-16 10:37:10

题意

  先定义了一个函数F(X)=An*2^n-1+An-1*2^n-2+.....+A1*1。其中Ai为X的第i位的值。对于每组数据给出了两个整数A,B。问不超过B的数中有多少的F值是不超过F(A)的。

分析

  经过计算我们发现,F(A)最大不会超过5000,于是我们可以把它加到记忆化里面。我们令dp[p][sum]为前p位数中不超过sum的数位多少。那么转移是很显然的

                                                              dp[p][sum]+=dp[p-1][sum-i*(1<<(p-1))]

 但是到这里还不是重点!重点是这个题有一个必须要明白才能过的技巧!我们可以把对dp数组的memset提到外面来,而不需要每一组输入都要初始化一次dp数组(这样会超时)。想一想为什么!这是这一类dp问题的一个共同技巧,这一类dp问题有个特点,dp的状态跟输入规模无关,只跟者这一位(或者几位)的值有关。

 

学数位dp一定做过那道hdu2089,那个题目也是如此,它记录的状态仅仅跟是不是这一位是不是4上一位是不是6有关系,而和输入规模无关,所以也可以把memset提出来。

 下面是hdu4734的代码

  

【HDU4734】F(x) 【数位dp】【HDU4734】F(x) 【数位dp】
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 const int maxn=5000;
 9 int T,A,B;
10 LL dp[15][maxn];
11 int a[15],pos;
12 LL F(int x){
13     int i=0;
14     LL res=0;
15     while(x){
16        res+=(x%10)*(1<<i);
17        i++;
18        x/=10;
19     }
20     return res;
21 }
22 LL dfs(int p,int sum,int limit){
23     if(p<=0&&sum>=0)
24         return 1;
25     if(!limit&&dp[p][sum]!=-1)
26         return dp[p][sum];
27     int up=limit?a[p]:9;
28     LL res=0;
29     for(int i=up;i>=0;i--){
30         if(sum-i*(1<<(p-1))<0)continue;
31         res+=dfs(p-1,sum-i*(1<<(p-1)),limit&&i==a[p]);
32     }
33     if(!limit)
34         dp[p][sum]=res;
35     return res;
36 }
37 LL solve(int x){
38     pos=0;
39     while(x){
40         a[++pos]=x%10;
41         x/=10;
42     }
43    // memset(dp,-1,sizeof(dp));//这里会出问题因为这个操作是O(14000)
44     return dfs(pos,F(A),1);
45 }
46 int main(){
47     scanf("%d",&T);
48     memset(dp,-1,sizeof(dp));
49     for(int t=1;t<=T;t++){
50         scanf("%d%d",&A,&B);
51        // printf("%lld\n",F(A));
52         printf("Case #%d: %lld\n",t,solve(B));
53     }
54 
55 return 0;
56 }
View Code