题目链接:https://vjudge.net/contest/308832#problem/H
题目大意:
定义
对于一个样例输入A B.
求[0, B]有多少个i使得:F(i)<=F(A)。
我们用一个sum来记录当前枚举数的F值,当pos=-1并且sum<=F(A)那么就return 1。这个状态dp[pos][sum]是和F(A)有关系的,所以对于不同的样例,就必须mem一次。
解决方法。我们用减法用ans=F(A)-sum来表示第二维状态。那么:ans表示到pos位, F(i) <=ans的个数, 就是下面的数的F(i)<=ans的i的个数。这个跟F(A)是无关的。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int aLL;//F(A)
int a[15];
int dp[15][100005];
int F(int x)
{
if(x==0)
{
return 0;
}
int ans=F(x/10);
return ans*2+(x%10);
}
int dfs(int pos, int sum, bool mt)
{
if(pos==-1)//满足条件
{
return sum<=aLL;
}
if(sum>aLL)//可行性剪枝
{
return 0;
}
if(!mt&&dp[pos][aLL-sum]!=-1)
{
return dp[pos][aLL-sum];
}
int Len=mt?a[pos]:9;
int ans=0;
for(int i=0;i<=Len;i++)
{
ans+=dfs(pos-1, sum+i*(1<<pos), mt&&i==a[pos]);
}
if(!mt)
{
dp[pos][aLL-sum]=ans;
}
return ans;
}
int slove(int x)
{
int pos=0;
while(x)
{
a[pos++]=x%10;
x/=10;
}
return dfs(pos-1, 0, true);
}
int main()
{
int T, CUT=1;
scanf("%d",&T);
memset(dp, -1, sizeof(dp));
while(T--)
{
int A, B;
scanf("%d%d",&A,&B);
aLL=F(A);
printf("Case #%d: %d\n", CUT++, slove(B));
}
return 0;
}