给一个数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 ;
}