|
数位dp模板：
typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
//递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
if(pos==-1) return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
/*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/
int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
ll ans=0;
//开始计数
for(int i=0;i=f(a)才是满足的条件。
#include
#include
#include
#include
using namespace std;
const int N=1e4+5;
int dp[12][N];
int f(int x)
{
if(x==0) return 0;
int ans=f(x/10);
return ans*2+(x%10);
}
int all;
int a[12];
int dfs(int pos,int sum,bool limit)
{
if(pos==-1) {return sumall) return 0;
if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];
int up=limit ? a[pos] : 9;
int ans=0;
for(int i=0;i=1;
}
return dfs(pos-1,32,true,true);
}
int main()
{
memset(dp,-1,sizeof dp);
int a,b;
while(~scanf("%d%d",&a,&b))
{
printf("%d\n",solve(b)-solve(a-1));
}
return 0;
}
|