bzoj1833: [ZJOI2010]count 数字计数(数位DP+记忆化搜索)

时间:2024-01-12 17:59:14

1833: [ZJOI2010]count 数字计数

题目:传送门


题解:

   今天是躲不开各种恶心DP了???

   %爆靖大佬啊!!!

   据说是数位DP裸题...emmm学吧学吧

   感觉记忆化搜索特别强:

   定义f[i][j][k]表示若前i个位置有k个j的此时的全局方案数,然后就可以记忆化搜索了(具体看代码吧)

  


代码:

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL f[][][],a[];
LL n,m;
LL dfs(int pos,int x,int sum,bool ld,bool lt)//ld表示当前情况是否要考虑前导0,lt表示的是枚举数字的上限是否有规定
{
if(pos==)return sum;
if(ld==false && lt==false && f[pos][x][sum]!=-)return f[pos][x][sum];
LL up=,ans=;if(lt==true)up=a[pos];
for(int i=;i<=up;i++)
{
int ss=sum;bool bk1=false,bk2=false;
if(i==x)ss++;
if(ld==true && i==){bk1=true;if(x==)ss--;}
if(lt==true && i==a[pos])bk2=true;
ans+=dfs(pos-,x,ss,bk1,bk2);
}
if(ld==false && lt==false)f[pos][x][sum]=ans;
return ans;
}
LL sol(LL x,int y)
{
int pos=;
while(x){a[++pos]=x%;x/=;}
return dfs(pos,y,,,);
}
int main()
{
memset(f,-,sizeof(f));
scanf("%lld%lld",&n,&m);
for(int i=;i<;i++)printf("%lld ",sol(m,i)-sol(n-,i));
printf("%lld\n",sol(m,)-sol(n-,));
return ;
}