hdu 4734 数位dp

时间:2022-03-05 23:39:15

给一个数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代码

 #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 ;
}