hdu 4734 数位dp

给一个数A (十进制表示形式为A_nA_n-1A_n-2 ... A₂A_{1，定义函数 F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 1，给一个B,求B以内的i,满足F(i)<=F(A)}

Sample Input

0 100

1 10

5 100

Sample Output

Case #1: 1

Case #2: 2

Case #3: 13

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

TLE代码

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 int a,b;

 int fa;         //fa的值

 int dp[][],digit[];

 int cal(int n)

 {

     int len=,sum=;

     while(n)

     {

         sum=sum+(n%)*(<<(len-));

         len++;

         n/=;

     }

     return sum;

 }

 int dfs(int p,int s,bool e) {   //位数，前面计算的和，任意填

     if(s>fa)    return ;

     if (p==-) return s<=fa;

     if (!e &&dp[p][s]!=-) return dp[p][s];

     int res = ;

     int u = e?digit[p]:;

     for (int d=;d<=u;++d)

     {

         int ns=s+d*(<<p);

         res+=dfs(p-,ns,e&&d==u);

     }

     return e?res:dp[p][s]=res;

 }

 int solve(int n)

 {

     int len=;

     while(n)

     {

         digit[len++]=n%;

         n/=;

     }

     return dfs(len-,,);

 }

 int main()

 {

     int t;

     //freopen("1.in","r",stdin);

     scanf("%d",&t);

     for(int i=;i<=t;i++)

     {

         memset(dp,-,sizeof(dp));

         scanf("%d%d",&a,&b);

         fa=cal(a);

         //printf("%d %d\n",a,fa);

         printf("Case #%d: %d\n",i,solve(b));

     }

     return ;

 }

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 int a,b;

 int fa;         //fa的值

 int dp[][],digit[];

 int cal(int n)

 {

     int len=,sum=;

     while(n)

     {

         sum=sum+(n%)*(<<(len-));

         len++;

         n/=;

     }

     return sum;

 }

 int dfs(int p,int s,bool e) {   //位数，小于s的数量，任意填

     if (p==-) return s>=;

     if(s<) return ;

     if (!e &&dp[p][s]!=-) return dp[p][s];

     int res = ;

     int u = e?digit[p]:;

     for (int d=;d<=u;++d)

     {

         int ns=s-d*(<<p);

         res+=dfs(p-,ns,e&&d==u);

     }

     return e?res:dp[p][s]=res;

 }

 int solve(int n)

 {

     int len=;

     while(n)

     {

         digit[len++]=n%;

         n/=;

     }

     return dfs(len-,fa,);

 }

 int main()

 {

     int t;

     //freopen("1.in","r",stdin);

     scanf("%d",&t);

     memset(dp,-,sizeof(dp));

     for(int i=;i<=t;i++)

     {

         scanf("%d%d",&a,&b);

         fa=cal(a);

         //printf("%d %d\n",a,fa);

         printf("Case #%d: %d\n",i,solve(b));

     }

     return ;

 }

巴特西

hdu 4734 数位dp

最新文章

热门文章