首页 > 代码库 > hdu 4734

hdu 4734

2024-11-24 01:05:02   203人阅读

给一个数A (十进制表示形式为AnAn-1An-2 ... A2A1，定义函数 F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1，给一个B,求B以内的i,满足F(i)<=F(A)

Sample Input

3
0 100
1 10
5 100
 
Sample Output
Case #1: 1
Case #2: 2
Case #3: 13
 
一开始状态s设置的是前面位数的和，但是这样每次dp对应的值都不同，需要重新清空，浪费了很多时间，于是重新设置s为小于s的数目，这样dp就不用每次重新计算，而达到记忆化搜索的效果，虽然仅仅改了几行代码，但速度快了很多，状态的设置要考虑好

 

TLE代码

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 int a,b; 8 int fa;         //fa的值 9 int dp[10][5000],digit[12];10 int cal(int n)11 {12     int len=1,sum=0;13     while(n)14     {15         sum=sum+(n%10)*(1<<(len-1));16         len++;17         n/=10;18     }19     return sum;20 }21 int dfs(int p,int s,bool e) {   //位数，前面计算的和，任意填22     if(s>fa)    return 0;23     if (p==-1) return s<=fa;24     if (!e &&dp[p][s]!=-1) return dp[p][s];25     int res = 0;26     int u = e?digit[p]:9;27     for (int d=0;d<=u;++d)28     {29         int ns=s+d*(1<<p);30         res+=dfs(p-1,ns,e&&d==u);31     }32     return e?res:dp[p][s]=res;33 }34 int solve(int n)35 {36     int len=0;37     while(n)38     {39         digit[len++]=n%10;40         n/=10;41     }42     return dfs(len-1,0,1);43 }44 int main()45 {46     int t;47     //freopen("1.in","r",stdin);48     scanf("%d",&t);49     for(int i=1;i<=t;i++)50     {51         memset(dp,-1,sizeof(dp));52         scanf("%d%d",&a,&b);53         fa=cal(a);54         //printf("%d %d\n",a,fa);55         printf("Case #%d: %d\n",i,solve(b));56     }57     return 0;58 }

AC代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 int a,b; 8 int fa;         //fa的值 9 int dp[12][10000],digit[12];10 int cal(int n)11 {12     int len=1,sum=0;13     while(n)14     {15         sum=sum+(n%10)*(1<<(len-1));16         len++;17         n/=10;18     }19     return sum;20 }21 int dfs(int p,int s,bool e) {   //位数，小于s的数量，任意填22     if (p==-1) return s>=0;23     if(s<0) return 0;24     if (!e &&dp[p][s]!=-1) return dp[p][s];25     int res = 0;26     int u = e?digit[p]:9;27     for (int d=0;d<=u;++d)28     {29         int ns=s-d*(1<<p);30         res+=dfs(p-1,ns,e&&d==u);31     }32     return e?res:dp[p][s]=res;33 }34 int solve(int n)35 {36     int len=0;37     while(n)38     {39         digit[len++]=n%10;40         n/=10;41     }42     return dfs(len-1,fa,1);43 }44 int main()45 {46     int t;47     //freopen("1.in","r",stdin);48     scanf("%d",&t);49     memset(dp,-1,sizeof(dp));50     for(int i=1;i<=t;i++)51     {52         scanf("%d%d",&a,&b);53         fa=cal(a);54         //printf("%d %d\n",a,fa);55         printf("Case #%d: %d\n",i,solve(b));56     }57     return 0;58 }

 

hdu 4734


联系
我们